diff options
| -rw-r--r-- | miasm2/analysis/depgraph.py | 327 | ||||
| -rw-r--r-- | test/analysis/depgraph.py | 1448 | ||||
| -rw-r--r-- | test/test_all.py | 31 |
3 files changed, 1289 insertions, 517 deletions
diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 1b1d7ed4..66c3f546 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -1,6 +1,7 @@ """Provide dependency graph""" import itertools -from collections import namedtuple +from collections import deque +from UserDict import IterableUserDict try: import z3 @@ -16,6 +17,7 @@ from miasm2.ir.ir import irbloc from miasm2.ir.translators import Translator class DependencyNode(object): + """Node elements of a DependencyGraph A dependency node stands for the dependency on the @element at line number @@ -23,7 +25,7 @@ class DependencyNode(object): line. """ - def __init__(self, label, element, line_nb, modifier=False): + def __init__(self, label, element, line_nb, step, modifier=False): """Create a dependency node with: @label: asm_label instance @element: Expr instance @@ -34,19 +36,30 @@ class DependencyNode(object): self._element = element self._line_nb = line_nb self._modifier = modifier - self._hash = hash((self._label, self._element, self._line_nb)) + self._step = step + self._nostep_repr = (self._label, self._line_nb, self._element) + self._hash = hash( + (self._label, self._element, self._line_nb, self._step)) def __hash__(self): + """Returns a hash of @self to uniquely identify @self""" return self._hash def __eq__(self, depnode): + """Returns True if @self and @depnode are equals. + The attribute 'step' is not considered in the comparison. + """ if not isinstance(depnode, self.__class__): return False return (self.label == depnode.label and self.element == depnode.element and - self.line_nb == depnode.line_nb) + self.line_nb == depnode.line_nb and + self.step == depnode.step) def __cmp__(self, node): + """Compares @self with @node. The step attribute is not taken into + account in the comparison. + """ if not isinstance(node, self.__class__): raise ValueError("Compare error between %s, %s" % (self.__class__, node.__class__)) @@ -54,14 +67,21 @@ class DependencyNode(object): (node.label, node.element, node.line_nb)) def __str__(self): - return "<%s %s %s %s M:%s>"%(self.__class__.__name__, - self.label.name, self.element, - self.line_nb, self.modifier) + """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) def __repr__(self): + """Returns a string representation of DependencyNode""" return self.__str__() @property + def nostep_repr(self): + """Returns a representation of @self ignoring the step attribute""" + return self._nostep_repr + + @property def label(self): "Name of the current IRBlock" return self._label @@ -77,6 +97,11 @@ class DependencyNode(object): return self._line_nb @property + def step(self): + "Step of the current node" + return self._step + + @property def modifier(self): """Evaluating the current line involves a modification of tracked dependencies""" @@ -84,12 +109,56 @@ 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") self._modifier = value +class CacheWrapper(IterableUserDict): + + """Wrapper class for cache dictionnary""" + + def __init__(self, dct=None): + """Create a CacheWrapper with value @dct.""" + IterableUserDict.__init__(self, dct) + self._nostep_cache = None + self._nostep_keys = None + + def __eq__(self, cache): + """Returns True if the nostep caches are equals""" + if self.nostep_keys != cache.nostep_keys: + return False + return self.nostep_cache == cache.nostep_cache + + @property + def nostep_keys(self): + """List of dictonnary keys without the step attribute. + The list is generated once when the method is called and not updated + afterward. + """ + if self._nostep_keys is None: + self._nostep_keys = set([key.nostep_repr for key in self.data]) + return self._nostep_keys + + @property + def nostep_cache(self): + """Dictionnary of DependencyNode and their dependencies, + without the step attribute. + The dictionnary is generated once when the method is called for the + first time and not updated afterward. + """ + if self._nostep_cache is None: + 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])) + return self._nostep_cache + + class DependencyDict(object): + """Internal structure for the DependencyGraph algorithm""" def __init__(self, label, history): @@ -102,14 +171,13 @@ class DependencyDict(object): self._pending = set() # DepNode -> set(DepNode) - self._cache = {} + self._cache = CacheWrapper() def __eq__(self, depdict): if not isinstance(depdict, self.__class__): return False return (self._label == depdict.label and - self._cache == depdict.cache and - self._pending == depdict.pending) + self.cache == depdict.cache) def __cmp__(self, depdict): if not isinstance(depdict, self.__class__): @@ -192,13 +260,13 @@ class DependencyDict(object): dependencies = self._cache[depnode] out = set() - ## Launch on each depnodes + # Launch on each depnodes parallels = [] for depnode in dependencies: parallels.append(self._get_modifiers_in_cache(depnode)) if parallels: - for parallel in itertools.product(*parallels): + for parallel in itertools.product(*[p for p in parallels if p]): out.update(parallel) return out @@ -207,13 +275,13 @@ class DependencyDict(object): """Remove intermediary states (non modifier depnodes) in the internal cache values""" - cache_out = {} - for depnode in self._cache.keys(): + cache_out = CacheWrapper() + for depnode in self._cache: cache_out[depnode] = self._get_modifiers_in_cache(depnode, force=True) self._cache = cache_out - def _build_depGraph(self, depnode): + def _build_depgraph(self, depnode): """Recursively build the final list of DiGraph, and clean up unmodifier nodes @depnode: starting node @@ -221,7 +289,7 @@ class DependencyDict(object): if depnode not in self._cache or \ not self._cache[depnode]: - ## There is no dependency + # There is no dependency graph = DiGraph() graph.add_node(depnode) return graph @@ -231,7 +299,7 @@ class DependencyDict(object): graphs = [] for sub_depnode in dependencies: - graphs.append(self._build_depGraph(sub_depnode)) + graphs.append(self._build_depgraph(sub_depnode)) # head(graphs[i]) == dependencies[i] graph = DiGraph() @@ -258,7 +326,7 @@ class DependencyDict(object): # Build subgraph for each starting_node subgraphs = [] for starting_node in starting_nodes: - subgraphs.append(self._build_depGraph(starting_node)) + subgraphs.append(self._build_depgraph(starting_node)) # Merge subgraphs into a final DiGraph graph = DiGraph() @@ -294,8 +362,77 @@ class DependencyDict(object): if key not in used_nodes: del self._cache[key] + def filter_unmodifier_loops(self, implicit, irdst): + """ + Remove unmodifier node creating dependency loops over + pending elements in cache. + """ + + previous_dict = None + # Get pending nodes of last time the label was handled + for hist_dict in reversed(self.history): + if hist_dict.label == self.label: + previous_dict = hist_dict + break + + if not previous_dict: + return + + nostep_pending = [node.nostep_repr for node in self.pending] + + to_remove = set() + for depnode in previous_dict.pending: + if (depnode.nostep_repr not in nostep_pending or + implicit and depnode.element == irdst): + continue + + to_remove.update(self._non_modifier_in_loop(depnode)) + + # Remove unused elements + 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) + if self._cache.has_key(key): + del self._cache[key] + + def _non_modifier_in_loop(self, depnode): + """ + 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. + """ + if not self.cache.has_key(depnode): + return set() + # Init + todo = set(self.cache[depnode]) + unmodifier_nodes = [] + + # Map + while todo: + node = todo.pop() + if node in unmodifier_nodes: + continue + if node.modifier: + return set() + unmodifier_nodes.append(node) + if not node in self._cache: + continue + if node.nostep_repr == depnode.nostep_repr: + unmodifier_nodes.append(node) + break + + for sub_node in self._cache[node]: + todo.add(sub_node) + + return unmodifier_nodes + class DependencyResult(object): + """Container and methods for DependencyGraph results""" def __init__(self, ira, final_depdict, input_depnodes): @@ -315,21 +452,27 @@ class DependencyResult(object): @property def graph(self): - "Lazy" + """Returns a DiGraph instance representing the DependencyGraph""" if self._graph is None: self._graph = self._depdict.as_graph(self._input_depnodes) return self._graph @property def history(self): + """List of depdict corresponding to the blocks encountered in the + analysis""" return list(self._depdict.history) + [self._depdict] @property def unresolved(self): - return set(self._depdict.pending) + """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]) @property def relevant_nodes(self): + """Set of nodes directly and indirectly influencing + @self.input_depnodes""" output = set() for depnodes in self._depdict.cache.values(): output.update(depnodes) @@ -337,28 +480,41 @@ class DependencyResult(object): @property def relevant_labels(self): + """List of labels containing nodes influencing @self.input_depnodes. + The history order is preserved. + """ # Get used labels used_labels = set([depnode.label for depnode in self.relevant_nodes]) # Keep history order output = [] for label in [depdict.label for depdict in self.history]: - if label not in output and label in used_labels: + if label in used_labels: output.append(label) return output @property def input(self): + """Set of DependencyGraph start nodes""" return self._input_depnodes + @property + def has_loop(self): + """True if current dictionnary has a loop""" + if self._has_loop is None: + self._has_loop = (len(self.relevant_labels) != + len(set(self.relevant_labels))) + return self._has_loop + def emul(self, ctx=None, step=False): """Symbolic execution of relevant nodes according to the history Return the values of input nodes' elements @ctx: (optional) Initial context as dictionnary @step: (optional) Verbose execution - /!\ The emulation is not safe if there is a loop in the relevant labels + Warning: The emulation is not sound if the input nodes depend on loop + variant. """ # Init ctx_init = self._ira.arch.regs.regs_init @@ -377,15 +533,16 @@ class DependencyResult(object): # Eval the block temp_label = asm_label("Temp") - sb = symbexec(self._ira, ctx_init) - sb.emulbloc(irbloc(temp_label, affects), step=step) + symb_exec = symbexec(self._ira, ctx_init) + symb_exec.emulbloc(irbloc(temp_label, affects), step=step) # Return only inputs values (others could be wrongs) - return {depnode.element: sb.symbols[depnode.element] + return {depnode.element: symb_exec.symbols[depnode.element] for depnode in self.input} class DependencyResultImplicit(DependencyResult): + """Stand for a result of a DependencyGraph with implicit option Provide path constraints using the z3 solver""" @@ -400,7 +557,7 @@ class DependencyResultImplicit(DependencyResult): ctx_init.update(ctx) depnodes = self.relevant_nodes solver = z3.Solver() - sb = symbexec(self._ira, ctx_init) + symb_exec = symbexec(self._ira, ctx_init) temp_label = asm_label("Temp") history = self.relevant_labels[::-1] history_size = len(history) @@ -416,12 +573,12 @@ class DependencyResultImplicit(DependencyResult): affects.append(irs[line_nb]) # Emul the block and get back destination - dst = sb.emulbloc(irbloc(temp_label, affects), step=step) + dst = symb_exec.emulbloc(irbloc(temp_label, affects), step=step) # Add constraint if hist_nb + 1 < history_size: next_label = history[hist_nb + 1] - expected = sb.eval_expr(m2_expr.ExprId(next_label, 32)) + expected = symb_exec.eval_expr(m2_expr.ExprId(next_label, 32)) constraint = m2_expr.ExprAff(dst, expected) solver.add(Translator.to_language("z3").from_expr(constraint)) @@ -429,7 +586,7 @@ class DependencyResultImplicit(DependencyResult): self._solver = solver # Return only inputs values (others could be wrongs) - return {depnode.element: sb.symbols[depnode.element] + return {depnode.element: symb_exec.symbols[depnode.element] for depnode in self.input} @property @@ -448,6 +605,7 @@ class DependencyResultImplicit(DependencyResult): class FollowExpr(object): + "Stand for an element (expression, depnode, ...) to follow or not" def __init__(self, follow, element): @@ -455,7 +613,7 @@ class FollowExpr(object): self.element = element @staticmethod - def to_depnodes(follow_exprs, label, line, modifier): + def to_depnodes(follow_exprs, label, line, modifier, counter): """Build a set of FollowExpr(DependencyNode) from the @follow_exprs set of FollowExpr""" dependencies = set() @@ -464,6 +622,7 @@ class FollowExpr(object): DependencyNode(label, follow_expr.element, line, + next(counter), modifier=modifier))) return dependencies @@ -477,6 +636,7 @@ class FollowExpr(object): class DependencyGraph(object): + """Implementation of a dependency graph A dependency graph contains DependencyNode as nodes. The oriented edges @@ -501,9 +661,10 @@ class DependencyGraph(object): # Init self._ira = ira self._implicit = implicit + self._step_counter = itertools.count() # The IRA graph must be computed - assert(hasattr(self._ira, 'g')) + assert hasattr(self._ira, 'g') # Create callback filters. The order is relevant. self._cb_follow = [] @@ -517,6 +678,11 @@ class DependencyGraph(object): self._cb_follow.append(self._follow_nocall) self._cb_follow.append(self._follow_label) + @property + def step_counter(self): + "Iteration counter" + return self._step_counter + @staticmethod def _follow_simp_expr(exprs): """Simplify expression so avoid tracking useless elements, @@ -531,16 +697,15 @@ class DependencyGraph(object): def _follow_label(exprs): """Do not follow labels""" follow = set() - unfollow = set() for expr in exprs: - if expr_is_label(expr): - unfollow.add(expr) - else: + if not expr_is_label(expr): follow.add(expr) - return follow, unfollow + + return follow, set() @staticmethod def _follow_mem_wrapper(exprs, mem_read): + """Wrapper to follow or not expression from memory pointer""" follow = set() for expr in exprs: follow.update(expr.get_r(mem_read=mem_read, cst_read=True)) @@ -569,16 +734,17 @@ class DependencyGraph(object): return follow, nofollow def _follow_apply_cb(self, expr): + """Apply callback functions to @expr + @expr : FollowExpr instance""" follow = set([expr]) nofollow = set() - for cb in self._cb_follow: - follow, nofollow_tmp = cb(follow) + for callback in self._cb_follow: + follow, nofollow_tmp = callback(follow) nofollow.update(nofollow_tmp) out = set(FollowExpr(True, expr) for expr in follow) out.update(set(FollowExpr(False, expr) for expr in nofollow)) - return out def _get_irs(self, label): @@ -590,8 +756,9 @@ class DependencyGraph(object): LINE_NB must be > 0""" return self._get_irs(depnode.label)[depnode.line_nb - 1] - def _resolve_depNode(self, depnode): - """Compute and return the dependencies involved by @depnode + def _direct_depnode_dependencies(self, depnode): + """Compute and return the dependencies involved by @depnode, + over the instruction @depnode.line_,. Return a set of FollowExpr""" if isinstance(depnode.element, m2_expr.ExprInt): @@ -604,9 +771,8 @@ class DependencyGraph(object): else: # Intra-block resolving - ## Get dependencies + # Get dependencies read = set() - modifier = False for affect in self._get_affblock(depnode): @@ -615,18 +781,20 @@ class DependencyGraph(object): read.update(elements) modifier = True - ## If it's not a modifier affblock, reinject current element + # If it's not a modifier affblock, reinject current element if not modifier: read = set([FollowExpr(True, depnode.element)]) - ## Build output + # Build output output = FollowExpr.to_depnodes(read, depnode.label, - depnode.line_nb - 1, modifier) + depnode.line_nb - 1, modifier, + self.step_counter) return output - def _updateDependencyDict(self, depdict): - """Update DependencyDict until a fixed point is reached + def _resolve_intrablock_dep(self, depdict): + """Resolve the dependencies of nodes in @depdict.pending inside + @depdict.label until a fixed point is reached. @depdict: DependencyDict to update""" # Prepare the work list @@ -647,14 +815,14 @@ class DependencyGraph(object): continue # Find dependency of the current depnode - sub_depnodes = self._resolve_depNode(depnode) + sub_depnodes = self._direct_depnode_dependencies(depnode) depdict.cache[depnode] = FollowExpr.extract_depnodes(sub_depnodes) # Add to the worklist its dependencies todo.update(FollowExpr.extract_depnodes(sub_depnodes, only_follow=True)) - # Pending states will be override in cache + # Pending states will be overriden in cache for depnode in depdict.pending: try: del depdict.cache[depnode] @@ -669,9 +837,9 @@ class DependencyGraph(object): length = len(self._get_irs(pred_label)) yield (pred_label, length) - def _processInterBloc(self, depnodes, heads): - """Create a DependencyDict from @depnodes, and propagate DependencyDicts - through all blocs + def _compute_interblock_dep(self, depnodes, heads): + """Create a DependencyDict from @depnodes, and propagate + DependencyDicts through all blocs """ # Create an DependencyDict which will only contain our depnodes current_depdict = DependencyDict(list(depnodes)[0].label, []) @@ -679,16 +847,16 @@ class DependencyGraph(object): # Init the work list done = {} - todo = [current_depdict] + todo = deque([current_depdict]) while todo: - depdict = todo.pop() + depdict = todo.popleft() # Update the dependencydict until fixed point is reached - self._updateDependencyDict(depdict) + self._resolve_intrablock_dep(depdict) # Clean irrelevant path - depdict.filter_used_nodes(depnodes) + depdict.filter_unmodifier_loops(self._implicit, self._ira.IRDst) # Avoid infinite loops label = depdict.label @@ -708,30 +876,32 @@ class DependencyGraph(object): for label, irb_len in self._get_previousblocks(depdict.label): is_final = False - ## Duplicate the DependencyDict + # Duplicate the DependencyDict new_depdict = depdict.extend(label) if self._implicit: - ### Implicit dependencies: IRDst will be link with heads + # Implicit dependencies: IRDst will be link with heads implicit_depnode = DependencyNode(label, self._ira.IRDst, - irb_len, modifier=False) - new_depdict.pending.add(implicit_depnode) + irb_len, + next(self.step_counter), + modifier=False) - ## Create links between DependencyDict + # Create links between DependencyDict for depnode_head in depdict.pending: - ### Follow the head element in the parent + # Follow the head element in the parent new_depnode = DependencyNode(label, depnode_head.element, - irb_len) - ### The new node has to be computed in _updateDependencyDict + irb_len, + next(self.step_counter)) + # The new node has to be analysed new_depdict.cache[depnode_head] = set([new_depnode]) new_depdict.pending.add(new_depnode) - ### Handle implicit dependencies + # Handle implicit dependencies if self._implicit: new_depdict.cache[depnode_head].add(implicit_depnode) + new_depdict.pending.add(implicit_depnode) - - ## Manage the new element + # Manage the new element todo.append(new_depdict) # Return the node if it's a final one, ie. it's a head (in graph @@ -753,26 +923,30 @@ class DependencyGraph(object): # Init the algorithm input_depnodes = set() for element in elements: - input_depnodes.add(DependencyNode(label, element, line_nb)) + input_depnodes.add(DependencyNode(label, element, line_nb, + next(self.step_counter))) # Compute final depdicts - depdicts = self._processInterBloc(input_depnodes, heads) + depdicts = self._compute_interblock_dep(input_depnodes, heads) # Unify solutions unified = [] - cls_res = DependencyResultImplicit if self._implicit else DependencyResult + cls_res = DependencyResultImplicit if self._implicit else \ + DependencyResult + for final_depdict in depdicts: - ## Keep only relevant nodes + # Keep only relevant nodes final_depdict.clean_modifiers_in_cache() final_depdict.filter_used_nodes(input_depnodes) - ## Remove duplicate solutions + # Remove duplicate solutions if final_depdict not in unified: unified.append(final_depdict) - ### Return solutions as DiGraph + + # Return solutions as DiGraph yield cls_res(self._ira, final_depdict, input_depnodes) - def get_fromDepNodes(self, depnodes, heads): + def get_from_depnodes(self, depnodes, heads): """Alias for the get() method. Use the attributes of @depnodes as argument. PRE: Labels and lines of depnodes have to be equals @@ -783,7 +957,7 @@ class DependencyGraph(object): elements = set([depnode.element for depnode in depnodes]) return self.get(lead.label, elements, lead.line_nb, heads) - def get_fromEnd(self, label, elements, heads): + def get_from_end(self, label, elements, heads): """Alias for the get() method. Consider that the dependency is asked at the end of the block named @label. @label: asm_label instance @@ -791,4 +965,3 @@ class DependencyGraph(object): @heads: set of asm_label instances """ return self.get(label, elements, len(self._get_irs(label)), heads) - diff --git a/test/analysis/depgraph.py b/test/analysis/depgraph.py index c5e41f64..86aa1749 100644 --- a/test/analysis/depgraph.py +++ b/test/analysis/depgraph.py @@ -1,72 +1,104 @@ -from miasm2.expression.expression import ExprId, ExprInt32, ExprAff +"""Regression test module for DependencyGraph""" +from miasm2.expression.expression import ExprId, ExprInt32, ExprAff, ExprCond from miasm2.core.asmbloc import asm_label from miasm2.ir.analysis import ira from miasm2.ir.ir import ir, irbloc from miasm2.core.graph import DiGraph -from miasm2.analysis.depgraph import DependencyNode, DependencyGraph, DependencyDict -from pdb import pm - -a = ExprId("a") -b = ExprId("b") -c = ExprId("c") -d = ExprId("d") - -a_init = ExprId("a_init") -b_init = ExprId("b_init") -c_init = ExprId("c_init") -d_init = ExprId("d_init") - -pc = ExprId("pc") -sp = ExprId("sp") - -cst1 = ExprInt32(0x11) -cst2 = ExprInt32(0x12) -cst3 = ExprInt32(0x13) - -lbl0 = asm_label("lbl0") -lbl1 = asm_label("lbl1") -lbl2 = asm_label("lbl2") -lbl3 = asm_label("lbl3") -lbl4 = asm_label("lbl4") -lbl5 = asm_label("lbl5") -lbl6 = asm_label("lbl6") - +from miasm2.analysis.depgraph import DependencyNode, DependencyGraph,\ + DependencyDict +from itertools import count + +STEP_COUNTER = count() +A = ExprId("a") +B = ExprId("b") +C = ExprId("c") +D = ExprId("d") +R = ExprId("r") + +A_INIT = ExprId("a_init") +B_INIT = ExprId("b_init") +C_INIT = ExprId("c_init") +D_INIT = ExprId("d_init") + +PC = ExprId("pc") +SP = ExprId("sp") + +CST1 = ExprInt32(0x11) +CST2 = ExprInt32(0x12) +CST3 = ExprInt32(0x13) +CST22 = ExprInt32(0x22) +CST23 = ExprInt32(0x23) +CST24 = ExprInt32(0x24) +CST33 = ExprInt32(0x33) +CST35 = ExprInt32(0x35) +CST37 = ExprInt32(0x37) + +LBL0 = asm_label("lbl0") +LBL1 = asm_label("lbl1") +LBL2 = asm_label("lbl2") +LBL3 = asm_label("lbl3") +LBL4 = asm_label("lbl4") +LBL5 = asm_label("lbl5") +LBL6 = asm_label("lbl6") def gen_irbloc(lbl, exprs): - lines = [None for i in xrange(len(exprs))] - irb = irbloc(lbl, exprs, lines) - return irb + """ Returns an IRBlock with empty lines. + Used only for tests purpose + """ + lines = [None for _ in xrange(len(exprs))] + return irbloc(lbl, exprs, lines) class Regs(object): - regs_init = {a: a_init, b: b_init, c: c_init, d: d_init} + + """Fake registers for tests """ + regs_init = {A: A_INIT, B: B_INIT, C: C_INIT, D: D_INIT} + all_regs_ids = [A, B, C, D, SP, PC, R] + class Arch(object): + + """Fake architecture for tests """ regs = Regs() def getpc(self, attrib): - return pc + return PC def getsp(self, attrib): - return sp + return SP + class IRATest(ir, ira): + """Fake IRA class for tests""" + def __init__(self, symbol_pool=None): arch = Arch() ir.__init__(self, arch, 32, symbol_pool) - self.IRDst = pc + self.IRDst = PC + self.ret_reg = R + + def get_out_regs(self, _): + return set([self.ret_reg, self.sp]) + class GraphTest(DiGraph): - def __init__(self, ira): - self.ira = ira + + """Fake graph representation class for test cases""" + + def __init__(self, pira): + self.ira = pira super(GraphTest, self).__init__() def __eq__(self, graph): - if self._nodes != graph._nodes: + if (sorted([node.nostep_repr for node in self._nodes]) + != sorted([node.nostep_repr for node in graph.nodes])): return False - if sorted(self._edges) != sorted(graph._edges): + if (sorted([(src.nostep_repr, dst.nostep_repr) + for (src, dst) in self._edges]) + != sorted([(src.nostep_repr, dst.nostep_repr) + for (src, dst) in graph.edges()])): return False return True @@ -76,566 +108,1134 @@ class GraphTest(DiGraph): else: return str(self.ira.blocs[node]) + class DepNodeTest(DiGraph): - def __init__(self, ira): - self.ira = ira + + """Fake graph class to represent expected test results""" + + def __init__(self, pira): + self.ira = pira super(DepNodeTest, self).__init__() def __eq__(self, graph): - if self._nodes != graph._nodes: + if (len(self._nodes) != len(graph.nodes()) or + len(self._edges) != len(graph.edges())): + return False + + if (set([n.nostep_repr for n in self._nodes]) != + set([n.nostep_repr for n in graph.nodes()])): return False - if sorted(self._edges) != sorted(graph._edges): + if (sorted([(src.nostep_repr, dst.nostep_repr) + for (src, dst) in self._edges]) + != sorted([(src.nostep_repr, dst.nostep_repr) + for (src, dst) in graph.edges()])): return False return True def node2str(self, node): - assert(node.label in self.ira.blocs) - out = "(%s, %s, %s)\\l"%(node.label.name, + assert node.label in self.ira.blocs + out = "(%s, %s, %s)\\l" % (node.label.name, node.element, node.line_nb) - if not (0 <= node.line_nb < len(self.ira.blocs[node.label].irs)): + if not 0 <= node.line_nb < len(self.ira.blocs[node.label].irs): return out exprs = self.ira.blocs[node.label].irs[node.line_nb] exprs_str = '\\l'.join([str(x) for x in exprs]) - return "%s %s"%(out, exprs_str) + return "%s %s" % (out, exprs_str) # Test structures print "[+] Test structures" print "[+] Test DependencyDict" -dd0 = DependencyDict(lbl0, []) -depnodes_0 = [DependencyNode(lbl0, a, i) for i in xrange(10)][::-1] - -## Heads -assert(list(dd0.heads()) == []) -assert(dd0.is_head(depnodes_0[-1]) == True) -assert(dd0.is_head(depnodes_0[0]) == False) -dd0.cache[depnodes_0[-1]] = set(depnodes_0[-1:]) -assert(list(dd0.heads()) == [depnodes_0[-1]]) - -## Extend -dd1 = dd0.extend(lbl1) - -assert(dd1.label == lbl1) -assert(dd1.history == [dd0]) -assert(dd1.cache == dd0.cache) -assert(dd1.pending == set()) -assert(dd1 != dd0) - -dd1.cache[depnodes_0[4]] = set(depnodes_0[5:9]) -assert(dd1.cache != dd0.cache) - -dd2 = dd0.copy() -assert(dd2.label == lbl0) -assert(dd2.history == []) -assert(dd2.cache == dd0.cache) -assert(dd2.pending == dd0.pending) -assert(dd2 == dd0) - -dd2.cache[depnodes_0[4]] = set(depnodes_0[5:9]) -assert(dd2.cache != dd0.cache) +DD0 = DependencyDict(LBL0, []) +DEPNODES_0 = [DependencyNode(LBL0, A, linenb, next(STEP_COUNTER)) + for linenb in xrange(10)][::-1] + +# Heads +assert list(DD0.heads()) == [] +assert DD0.is_head(DEPNODES_0[-1]) == True +assert DD0.is_head(DEPNODES_0[0]) == False +DD0.cache[DEPNODES_0[-1]] = set(DEPNODES_0[-1:]) +assert list(DD0.heads()) == [DEPNODES_0[-1]] + +# Extend +DD1 = DD0.extend(LBL1) + +assert DD1.label == LBL1 +assert DD1.history == [DD0] +assert DD1.cache == DD0.cache +assert DD1.pending == set() +assert DD1 != DD0 + +DD1.cache[DEPNODES_0[4]] = set(DEPNODES_0[5:9]) +assert DD1.cache != DD0.cache + +DD2 = DD0.copy() +assert DD2.label == LBL0 +assert DD2.history == [] +assert DD2.cache == DD0.cache +assert DD2.pending == DD0.pending +assert DD2 == DD0 + +DD2.cache[DEPNODES_0[4]] = set(DEPNODES_0[5:9]) +assert DD2.cache != DD0.cache + + +print " [+] Test dictionnary equality" +DNA = DependencyNode(LBL2, A, 0, next(STEP_COUNTER)) +DNB = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) +DNC = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) +DNB2 = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) +DNC2 = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) +DNB3 = DependencyNode(LBL1, B, 1, next(STEP_COUNTER)) +DNC3 = DependencyNode(LBL1, C, 0, next(STEP_COUNTER), True) + +DDCT1 = DependencyDict(LBL1, []) +DDCT1.cache.update({DNA: set([DNB]), DNB: set([DNC])}) + +DDCT2 = DDCT1.extend(LBL1) +DDCT2.cache.update({DNA: set([DNB]), DNB: set([DNC]), + DNC: set([DNB2]), DNB2: set([DNC2]) + }) + +DDCT3 = DDCT2.extend(LBL1) +DDCT3.cache.update( + {DNA: set([DNB]), DNB: set([DNC]), + DNC: set([DNB2]), DNB2: set([DNC2]), + DNC2: set([DNB3]), DNB3: set([DNC3])}) + +assert not DDCT1.__eq__(DDCT2) +assert DDCT2.__eq__(DDCT3) print "[+] DependencyDict OK !" print "[+] Structures OK !" # graph 1 -g1_ira = IRATest() -g1_ira.g = GraphTest(g1_ira) +G1_IRA = IRATest() +G1_IRA.g = GraphTest(G1_IRA) -g1_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g1_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)] ]) -g1_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) +G1_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G1_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)]]) +G1_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) -g1_ira.g.add_uniq_edge(g1_irb0.label, g1_irb1.label) -g1_ira.g.add_uniq_edge(g1_irb1.label, g1_irb2.label) +G1_IRA.g.add_uniq_edge(G1_IRB0.label, G1_IRB1.label) +G1_IRA.g.add_uniq_edge(G1_IRB1.label, G1_IRB2.label) -g1_ira.blocs = dict([(irb.label, irb) for irb in [g1_irb0, g1_irb1, g1_irb2]]) +G1_IRA.blocs = dict([(irb.label, irb) for irb in [G1_IRB0, G1_IRB1, G1_IRB2]]) # graph 2 -g2_ira = IRATest() -g2_ira.g = GraphTest(g2_ira) +G2_IRA = IRATest() +G2_IRA.g = GraphTest(G2_IRA) -g2_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g2_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, cst2)] ]) -g2_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b+c)] ]) +G2_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G2_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, CST2)]]) +G2_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B + C)]]) -g2_ira.g.add_uniq_edge(g2_irb0.label, g2_irb1.label) -g2_ira.g.add_uniq_edge(g2_irb1.label, g2_irb2.label) +G2_IRA.g.add_uniq_edge(G2_IRB0.label, G2_IRB1.label) +G2_IRA.g.add_uniq_edge(G2_IRB1.label, G2_IRB2.label) -g2_ira.blocs = dict([(irb.label, irb) for irb in [g2_irb0, g2_irb1, g2_irb2]]) +G2_IRA.blocs = dict([(irb.label, irb) for irb in [G2_IRB0, G2_IRB1, G2_IRB2]]) # graph 3 -g3_ira = IRATest() -g3_ira.g = GraphTest(g3_ira) +G3_IRA = IRATest() +G3_IRA.g = GraphTest(G3_IRA) -g3_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g3_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, cst2)] ]) -g3_irb2 = gen_irbloc(lbl2, [ [ExprAff(b, cst3)] ]) -g3_irb3 = gen_irbloc(lbl3, [ [ExprAff(a, b+c)] ]) +G3_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G3_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, CST2)]]) +G3_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, CST3)]]) +G3_IRB3 = gen_irbloc(LBL3, [[ExprAff(A, B + C)]]) -g3_ira.g.add_uniq_edge(g3_irb0.label, g3_irb1.label) -g3_ira.g.add_uniq_edge(g3_irb0.label, g3_irb2.label) -g3_ira.g.add_uniq_edge(g3_irb1.label, g3_irb3.label) -g3_ira.g.add_uniq_edge(g3_irb2.label, g3_irb3.label) +G3_IRA.g.add_uniq_edge(G3_IRB0.label, G3_IRB1.label) +G3_IRA.g.add_uniq_edge(G3_IRB0.label, G3_IRB2.label) +G3_IRA.g.add_uniq_edge(G3_IRB1.label, G3_IRB3.label) +G3_IRA.g.add_uniq_edge(G3_IRB2.label, G3_IRB3.label) -g3_ira.blocs = dict([(irb.label, irb) for irb in [g3_irb0, g3_irb1, - g3_irb2, g3_irb3]]) +G3_IRA.blocs = dict([(irb.label, irb) for irb in [G3_IRB0, G3_IRB1, + G3_IRB2, G3_IRB3]]) # graph 4 -g4_ira = IRATest() -g4_ira.g = GraphTest(g4_ira) +G4_IRA = IRATest() +G4_IRA.g = GraphTest(G4_IRA) -g4_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g4_irb1 = gen_irbloc(lbl1, [ [ExprAff(c, c+cst2)] ]) -g4_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) +G4_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G4_IRB1 = gen_irbloc(LBL1, [[ExprAff(C, C + CST2)]]) +G4_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) -g4_ira.g.add_uniq_edge(g4_irb0.label, g4_irb1.label) -g4_ira.g.add_uniq_edge(g4_irb1.label, g4_irb2.label) -g4_ira.g.add_uniq_edge(g4_irb1.label, g4_irb1.label) +G4_IRA.g.add_uniq_edge(G4_IRB0.label, G4_IRB1.label) +G4_IRA.g.add_uniq_edge(G4_IRB1.label, G4_IRB2.label) +G4_IRA.g.add_uniq_edge(G4_IRB1.label, G4_IRB1.label) -g4_ira.blocs = dict([(irb.label, irb) for irb in [g4_irb0, g4_irb1, g4_irb2]]) +G4_IRA.blocs = dict([(irb.label, irb) for irb in [G4_IRB0, G4_IRB1, G4_IRB2]]) # graph 5 -g5_ira = IRATest() -g5_ira.g = GraphTest(g5_ira) +G5_IRA = IRATest() +G5_IRA.g = GraphTest(G5_IRA) -g5_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ]) -g5_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ]) -g5_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) +G5_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) +G5_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, B + CST2)]]) +G5_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) -g5_ira.g.add_uniq_edge(g5_irb0.label, g5_irb1.label) -g5_ira.g.add_uniq_edge(g5_irb1.label, g5_irb2.label) -g5_ira.g.add_uniq_edge(g5_irb1.label, g5_irb1.label) +G5_IRA.g.add_uniq_edge(G5_IRB0.label, G5_IRB1.label) +G5_IRA.g.add_uniq_edge(G5_IRB1.label, G5_IRB2.label) +G5_IRA.g.add_uniq_edge(G5_IRB1.label, G5_IRB1.label) -g5_ira.blocs = dict([(irb.label, irb) for irb in [g5_irb0, g5_irb1, g5_irb2]]) +G5_IRA.blocs = dict([(irb.label, irb) for irb in [G5_IRB0, G5_IRB1, G5_IRB2]]) # graph 6 -g6_ira = IRATest() -g6_ira.g = GraphTest(g6_ira) +G6_IRA = IRATest() +G6_IRA.g = GraphTest(G6_IRA) -g6_irb0 = gen_irbloc(lbl0, [ [ExprAff(b, cst1)] ]) -g6_irb1 = gen_irbloc(lbl1, [ [ExprAff(a, b)] ]) +G6_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) +G6_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B)]]) -g6_ira.g.add_uniq_edge(g6_irb0.label, g6_irb1.label) -g6_ira.g.add_uniq_edge(g6_irb1.label, g6_irb1.label) +G6_IRA.g.add_uniq_edge(G6_IRB0.label, G6_IRB1.label) +G6_IRA.g.add_uniq_edge(G6_IRB1.label, G6_IRB1.label) -g6_ira.blocs = dict([(irb.label, irb) for irb in [g6_irb0, g6_irb1]]) +G6_IRA.blocs = dict([(irb.label, irb) for irb in [G6_IRB0, G6_IRB1]]) # graph 7 -g7_ira = IRATest() -g7_ira.g = GraphTest(g7_ira) +G7_IRA = IRATest() +G7_IRA.g = GraphTest(G7_IRA) -g7_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g7_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)], [ExprAff(a, b)] ]) -g7_irb2 = gen_irbloc(lbl2, [ [ExprAff(d, a)] ]) +G7_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G7_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)], [ExprAff(A, B)]]) +G7_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)]]) -g7_ira.g.add_uniq_edge(g7_irb0.label, g7_irb1.label) -g7_ira.g.add_uniq_edge(g7_irb1.label, g7_irb1.label) -g7_ira.g.add_uniq_edge(g7_irb1.label, g7_irb2.label) +G7_IRA.g.add_uniq_edge(G7_IRB0.label, G7_IRB1.label) +G7_IRA.g.add_uniq_edge(G7_IRB1.label, G7_IRB1.label) +G7_IRA.g.add_uniq_edge(G7_IRB1.label, G7_IRB2.label) -g7_ira.blocs = dict([(irb.label, irb) for irb in [g7_irb0, g7_irb1, g7_irb2]]) +G7_IRA.blocs = dict([(irb.label, irb) for irb in [G7_IRB0, G7_IRB1, G7_IRB2]]) # graph 8 -g8_ira = IRATest() -g8_ira.g = GraphTest(g8_ira) +G8_IRA = IRATest() +G8_IRA.g = GraphTest(G8_IRA) -g8_irb0 = gen_irbloc(lbl0, [ [ExprAff(c, cst1)] ]) -g8_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, c)], [ExprAff(c, d)] ]) -g8_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) +G8_IRB0 = gen_irbloc(LBL0, [[ExprAff(C, CST1)]]) +G8_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, C)], [ExprAff(C, D)]]) +G8_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) -g8_ira.g.add_uniq_edge(g8_irb0.label, g8_irb1.label) -g8_ira.g.add_uniq_edge(g8_irb1.label, g8_irb1.label) -g8_ira.g.add_uniq_edge(g8_irb1.label, g8_irb2.label) +G8_IRA.g.add_uniq_edge(G8_IRB0.label, G8_IRB1.label) +G8_IRA.g.add_uniq_edge(G8_IRB1.label, G8_IRB1.label) +G8_IRA.g.add_uniq_edge(G8_IRB1.label, G8_IRB2.label) -g8_ira.blocs = dict([(irb.label, irb) for irb in [g8_irb0, g8_irb1, g8_irb2]]) +G8_IRA.blocs = dict([(irb.label, irb) for irb in [G8_IRB0, G8_IRB1, G8_IRB2]]) # graph 9 is graph 8 # graph 10 -g10_ira = IRATest() -g10_ira.g = GraphTest(g10_ira) +G10_IRA = IRATest() +G10_IRA.g = GraphTest(G10_IRA) -g10_irb1 = gen_irbloc(lbl1, [ [ExprAff(b, b+cst2)] ]) -g10_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, b)] ]) +G10_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, B + CST2)]]) +G10_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, B)]]) -g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb2.label) -g10_ira.g.add_uniq_edge(g10_irb1.label, g10_irb1.label) +G10_IRA.g.add_uniq_edge(G10_IRB1.label, G10_IRB2.label) +G10_IRA.g.add_uniq_edge(G10_IRB1.label, G10_IRB1.label) -g10_ira.blocs = dict([(irb.label, irb) for irb in [g10_irb1, g10_irb2]]) +G10_IRA.blocs = dict([(irb.label, irb) for irb in [G10_IRB1, G10_IRB2]]) # graph 11 -g11_ira = IRATest() -g11_ira.g = GraphTest(g11_ira) +G11_IRA = IRATest() +G11_IRA.g = GraphTest(G11_IRA) + +G11_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1), + ExprAff(B, CST2)]]) +G11_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B), + ExprAff(B, A)]]) +G11_IRB2 = gen_irbloc(LBL2, [[ExprAff(A, A - B)]]) + +G11_IRA.g.add_uniq_edge(G11_IRB0.label, G11_IRB1.label) +G11_IRA.g.add_uniq_edge(G11_IRB1.label, G11_IRB2.label) + +G11_IRA.blocs = dict([(irb.label, irb) + for irb in [G11_IRB0, G11_IRB1, G11_IRB2]]) + +# graph 12 + +G12_IRA = IRATest() +G12_IRA.g = GraphTest(G12_IRA) + +G12_IRB0 = gen_irbloc(LBL0, [[ExprAff(B, CST1)]]) +G12_IRB1 = gen_irbloc(LBL1, [[ExprAff(A, B)], [ExprAff(B, B + CST2)]]) +G12_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, A)]]) + +G12_IRA.g.add_uniq_edge(G12_IRB0.label, G12_IRB1.label) +G12_IRA.g.add_uniq_edge(G12_IRB1.label, G12_IRB2.label) +G12_IRA.g.add_uniq_edge(G12_IRB1.label, G12_IRB1.label) + +G12_IRA.blocs = dict([(irb.label, irb) for irb in [G12_IRB0, G12_IRB1, + G12_IRB2]]) + + +# graph 13 + +G13_IRA = IRATest() +G13_IRA.g = GraphTest(G13_IRA) + +G13_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], + #[ExprAff(B, A)], + [ExprAff(G13_IRA.IRDst, + ExprId(LBL1))]]) +G13_IRB1 = gen_irbloc(LBL1, [[ExprAff(C, A)], + #[ExprAff(A, A + CST1)], + [ExprAff(G13_IRA.IRDst, + ExprCond(R, ExprId(LBL2), + ExprId(LBL1)))]]) -g11_irb0 = gen_irbloc(lbl0, [ [ExprAff(a, cst1), - ExprAff(b, cst2)] ]) -g11_irb1 = gen_irbloc(lbl1, [ [ExprAff(a, b), - ExprAff(b, a)] ]) -g11_irb2 = gen_irbloc(lbl2, [ [ExprAff(a, a - b)] ]) +G13_IRB2 = gen_irbloc(LBL2, [[ExprAff(B, A + CST3)], [ExprAff(A, B + CST3)], + [ExprAff(G13_IRA.IRDst, + ExprId(LBL1))]]) -g11_ira.g.add_uniq_edge(g11_irb0.label, g11_irb1.label) -g11_ira.g.add_uniq_edge(g11_irb1.label, g11_irb2.label) +G13_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, C)]]) -g11_ira.blocs = dict([(irb.label, irb) for irb in [g11_irb0, g11_irb1, g11_irb2]]) +G13_IRA.g.add_uniq_edge(G13_IRB0.label, G13_IRB1.label) +G13_IRA.g.add_uniq_edge(G13_IRB1.label, G13_IRB2.label) +G13_IRA.g.add_uniq_edge(G13_IRB2.label, G13_IRB1.label) +G13_IRA.g.add_uniq_edge(G13_IRB1.label, G13_IRB3.label) + +G13_IRA.blocs = dict([(irb.label, irb) for irb in [G13_IRB0, G13_IRB1, + G13_IRB2, G13_IRB3]]) + +# graph 14 + +G14_IRA = IRATest() +G14_IRA.g = GraphTest(G14_IRA) + +G14_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], + [ExprAff(G14_IRA.IRDst, + ExprId(LBL1))] + ]) +G14_IRB1 = gen_irbloc(LBL1, [[ExprAff(B, A)], + [ExprAff(G14_IRA.IRDst, + ExprCond(C, ExprId(LBL2), + ExprId(LBL3)))] + ]) + +G14_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)], + [ExprAff(A, D + CST1)], + [ExprAff(G14_IRA.IRDst, + ExprId(LBL1))] + ]) + +G14_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, D + B)]]) + +G14_IRA.g.add_uniq_edge(G14_IRB0.label, G14_IRB1.label) +G14_IRA.g.add_uniq_edge(G14_IRB1.label, G14_IRB2.label) +G14_IRA.g.add_uniq_edge(G14_IRB2.label, G14_IRB1.label) +G14_IRA.g.add_uniq_edge(G14_IRB1.label, G14_IRB3.label) + +G14_IRA.blocs = dict([(irb.label, irb) for irb in [G14_IRB0, G14_IRB1, + G14_IRB2, G14_IRB3]]) + +# graph 16 + +G15_IRA = IRATest() +G15_IRA.g = GraphTest(G15_IRA) + +G15_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) +G15_IRB1 = gen_irbloc(LBL1, [[ExprAff(D, A + B)], + [ExprAff(C, D)], + [ExprAff(B, C)]]) +G15_IRB2 = gen_irbloc(LBL2, [[ExprAff(R, B)]]) + +G15_IRA.g.add_uniq_edge(G15_IRB0.label, G15_IRB1.label) +G15_IRA.g.add_uniq_edge(G15_IRB1.label, G15_IRB2.label) +G15_IRA.g.add_uniq_edge(G15_IRB1.label, G15_IRB1.label) + +G15_IRA.blocs = dict([(irb.label, irb) for irb in [G15_IRB0, G15_IRB1, + G15_IRB2]]) + +# graph 16 + +G16_IRA = IRATest() +G16_IRA.g = GraphTest(G16_IRA) + +G16_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)]]) +G16_IRB1 = gen_irbloc(LBL1, [[ExprAff(R, D)]]) +G16_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)]]) +G16_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, D)]]) +G16_IRB4 = gen_irbloc(LBL4, [[ExprAff(R, A)]]) +G16_IRB5 = gen_irbloc(LBL5, [[ExprAff(R, A)]]) + +G16_IRA.g.add_uniq_edge(G16_IRB0.label, G16_IRB1.label) +G16_IRA.g.add_uniq_edge(G16_IRB1.label, G16_IRB2.label) +G16_IRA.g.add_uniq_edge(G16_IRB2.label, G16_IRB1.label) +G16_IRA.g.add_uniq_edge(G16_IRB1.label, G16_IRB3.label) +G16_IRA.g.add_uniq_edge(G16_IRB3.label, G16_IRB1.label) +G16_IRA.g.add_uniq_edge(G16_IRB1.label, G16_IRB4.label) +G16_IRA.g.add_uniq_edge(G16_IRB4.label, G16_IRB1.label) +G16_IRA.g.add_uniq_edge(G16_IRB1.label, G16_IRB5.label) + +G16_IRA.blocs = dict([(irb.label, irb) for irb in [G16_IRB0, G16_IRB1, + G16_IRB2, G16_IRB3, + G16_IRB4, G16_IRB5]]) + +# graph 17 + +G17_IRA = IRATest() +G17_IRA.g = GraphTest(G17_IRA) + +G17_IRB0 = gen_irbloc(LBL0, [[ExprAff(A, CST1)], + [ExprAff(G17_IRA.IRDst, + ExprId(LBL1))]]) +G17_IRB1 = gen_irbloc(LBL1, [[ExprAff(R, D)], + [ExprAff(G17_IRA.IRDst, + ExprCond(C, ExprId(LBL2), + ExprId(LBL1)))]]) + +G17_IRB2 = gen_irbloc(LBL2, [[ExprAff(D, A)], + [ExprAff(A, A + CST1)], + [ExprAff(G17_IRA.IRDst, + ExprId(LBL1))]]) + +G17_IRB3 = gen_irbloc(LBL3, [[ExprAff(R, A + D)]]) + +G17_IRA.g.add_uniq_edge(G17_IRB0.label, G17_IRB1.label) +G17_IRA.g.add_uniq_edge(G17_IRB1.label, G17_IRB2.label) +G17_IRA.g.add_uniq_edge(G17_IRB2.label, G17_IRB1.label) +G17_IRA.g.add_uniq_edge(G17_IRB1.label, G17_IRB3.label) + +G17_IRA.blocs = dict([(irb.label, irb) for irb in [G17_IRB0, G17_IRB1, + G17_IRB2, G17_IRB3]]) # Test graph 1 -g1_test1 = DepNodeTest(g1_ira) +G1_TEST1 = DepNodeTest(G1_IRA) + +G1_TEST1_DN1 = DependencyNode( + G1_IRB2.label, A, len(G1_IRB2.irs), next(STEP_COUNTER)) +G1_TEST1_DN2 = DependencyNode(G1_IRB2.label, B, 0, next(STEP_COUNTER)) +G1_TEST1_DN3 = DependencyNode(G1_IRB1.label, C, 0, next(STEP_COUNTER)) +G1_TEST1_DN4 = DependencyNode(G1_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g1_test1_dn1 = DependencyNode(g1_irb2.label, a, len(g1_irb2.irs)) -g1_test1_dn2 = DependencyNode(g1_irb2.label, b, 0) -g1_test1_dn3 = DependencyNode(g1_irb1.label, c, 0) -g1_test1_dn4 = DependencyNode(g1_irb0.label, cst1, 0) +G1_TEST1.add_uniq_edge(G1_TEST1_DN4, G1_TEST1_DN3) +G1_TEST1.add_uniq_edge(G1_TEST1_DN3, G1_TEST1_DN2) +G1_TEST1.add_uniq_edge(G1_TEST1_DN2, G1_TEST1_DN1) -g1_test1.add_uniq_edge(g1_test1_dn4, g1_test1_dn3) -g1_test1.add_uniq_edge(g1_test1_dn3, g1_test1_dn2) -g1_test1.add_uniq_edge(g1_test1_dn2, g1_test1_dn1) +G1_INPUT = (set([G1_TEST1_DN1]), set([G1_IRB0.label])) -g1_input = (set([g1_test1_dn1]), set([g1_irb0.label])) -g1_output1 = {"graph": g1_test1, - "emul": {a: cst1}, - "unresolved": set(), - "has_loop": False} +G1_OUTPUT = {"graph": [G1_TEST1], + "emul": [{A: CST1}], + "unresolved": [set()], + "has_loop": [False]} # Test graph 2 -g2_test1 = DepNodeTest(g2_ira) +G2_TEST1 = DepNodeTest(G2_IRA) -g2_test1_dn1 = DependencyNode(g2_irb2.label, a, len(g2_irb2.irs)) -g2_test1_dn2 = DependencyNode(g2_irb2.label, b, 0) -g2_test1_dn3 = DependencyNode(g2_irb2.label, c, 0) -g2_test1_dn4 = DependencyNode(g2_irb1.label, cst2, 0) -g2_test1_dn5 = DependencyNode(g2_irb0.label, cst1, 0) +G2_TEST1_DN1 = DependencyNode( + G2_IRB2.label, A, len(G2_IRB2.irs), next(STEP_COUNTER)) +G2_TEST1_DN2 = DependencyNode(G2_IRB2.label, B, 0, next(STEP_COUNTER)) +G2_TEST1_DN3 = DependencyNode(G2_IRB2.label, C, 0, next(STEP_COUNTER)) +G2_TEST1_DN4 = DependencyNode(G2_IRB1.label, CST2, 0, next(STEP_COUNTER)) +G2_TEST1_DN5 = DependencyNode(G2_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g2_test1.add_uniq_edge(g2_test1_dn5, g2_test1_dn3) -g2_test1.add_uniq_edge(g2_test1_dn4, g2_test1_dn2) -g2_test1.add_uniq_edge(g2_test1_dn2, g2_test1_dn1) -g2_test1.add_uniq_edge(g2_test1_dn3, g2_test1_dn1) +G2_TEST1.add_uniq_edge(G2_TEST1_DN5, G2_TEST1_DN3) +G2_TEST1.add_uniq_edge(G2_TEST1_DN4, G2_TEST1_DN2) +G2_TEST1.add_uniq_edge(G2_TEST1_DN2, G2_TEST1_DN1) +G2_TEST1.add_uniq_edge(G2_TEST1_DN3, G2_TEST1_DN1) -g2_input = (set([g2_test1_dn1]), set([g2_irb0.label])) -g2_output1 = {"graph": g2_test1, - "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))}, - "unresolved": set(), - "has_loop": False} +G2_INPUT = (set([G2_TEST1_DN1]), set([G2_IRB0.label])) +G2_OUTPUT = {"graph": [G2_TEST1], + "emul": [{A: ExprInt32(int(CST1.arg) + int(CST2.arg))}], + "unresolved": [set()], + "has_loop": [False]} # Test graph 3 -g3_test1_0 = DepNodeTest(g3_ira) -g3_test1_1 = DepNodeTest(g3_ira) +G3_TEST1_0 = DepNodeTest(G3_IRA) +G3_TEST1_1 = DepNodeTest(G3_IRA) -g3_test1_0_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs)) -g3_test1_0_dn2 = DependencyNode(g3_irb3.label, b, 0) -g3_test1_0_dn3 = DependencyNode(g3_irb3.label, c, 0) -g3_test1_0_dn4 = DependencyNode(g3_irb2.label, cst3, 0) -g3_test1_0_dn5 = DependencyNode(g3_irb0.label, cst1, 0) +G3_TEST1_0_DN1 = DependencyNode( + G3_IRB3.label, A, len(G3_IRB3.irs), next(STEP_COUNTER)) +G3_TEST1_0_DN2 = DependencyNode(G3_IRB3.label, B, 0, next(STEP_COUNTER)) +G3_TEST1_0_DN3 = DependencyNode(G3_IRB3.label, C, 0, next(STEP_COUNTER)) +G3_TEST1_0_DN4 = DependencyNode(G3_IRB2.label, CST3, 0, next(STEP_COUNTER)) +G3_TEST1_0_DN5 = DependencyNode(G3_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g3_test1_1_dn1 = DependencyNode(g3_irb3.label, a, len(g3_irb3.irs)) -g3_test1_1_dn2 = DependencyNode(g3_irb3.label, b, 0) -g3_test1_1_dn3 = DependencyNode(g3_irb3.label, c, 0) -g3_test1_1_dn4 = DependencyNode(g3_irb1.label, cst2, 0) -g3_test1_1_dn5 = DependencyNode(g3_irb0.label, cst1, 0) +G3_TEST1_1_DN2 = DependencyNode(G3_IRB3.label, B, 0, next(STEP_COUNTER)) +G3_TEST1_1_DN3 = DependencyNode(G3_IRB3.label, C, 0, next(STEP_COUNTER)) +G3_TEST1_1_DN4 = DependencyNode(G3_IRB1.label, CST2, 0, next(STEP_COUNTER)) +G3_TEST1_1_DN5 = DependencyNode(G3_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g3_test1_0.add_uniq_edge(g3_test1_0_dn5, g3_test1_0_dn3) -g3_test1_0.add_uniq_edge(g3_test1_0_dn4, g3_test1_0_dn2) -g3_test1_0.add_uniq_edge(g3_test1_0_dn2, g3_test1_0_dn1) -g3_test1_0.add_uniq_edge(g3_test1_0_dn3, g3_test1_0_dn1) +G3_TEST1_0.add_uniq_edge(G3_TEST1_0_DN5, G3_TEST1_0_DN3) +G3_TEST1_0.add_uniq_edge(G3_TEST1_0_DN4, G3_TEST1_0_DN2) +G3_TEST1_0.add_uniq_edge(G3_TEST1_0_DN2, G3_TEST1_0_DN1) +G3_TEST1_0.add_uniq_edge(G3_TEST1_0_DN3, G3_TEST1_0_DN1) -g3_test1_1.add_uniq_edge(g3_test1_1_dn5, g3_test1_1_dn3) -g3_test1_1.add_uniq_edge(g3_test1_1_dn4, g3_test1_1_dn2) -g3_test1_1.add_uniq_edge(g3_test1_1_dn2, g3_test1_1_dn1) -g3_test1_1.add_uniq_edge(g3_test1_1_dn3, g3_test1_0_dn1) +G3_TEST1_1.add_uniq_edge(G3_TEST1_1_DN5, G3_TEST1_1_DN3) +G3_TEST1_1.add_uniq_edge(G3_TEST1_1_DN4, G3_TEST1_1_DN2) +G3_TEST1_1.add_uniq_edge(G3_TEST1_1_DN2, G3_TEST1_0_DN1) +G3_TEST1_1.add_uniq_edge(G3_TEST1_1_DN3, G3_TEST1_0_DN1) -g3_input = (set([g3_test1_0_dn1]), set([g3_irb0.label])) +G3_INPUT = (set([G3_TEST1_0_DN1]), set([G3_IRB0.label])) -g3_output1 = {"graph": g3_test1_0, - "emul": {a: ExprInt32(int(cst1.arg) + int(cst3.arg))}, - "unresolved": set(), - "has_loop": False} - -g3_output2 = {"graph": g3_test1_1, - "emul": {a: ExprInt32(int(cst1.arg) + int(cst2.arg))}, - "unresolved": set(), - "has_loop": False} +G3_OUTPUT = {"graph": [G3_TEST1_0, G3_TEST1_1], + "emul": [{A: ExprInt32(int(CST1.arg) + int(CST3.arg))}, + {A: ExprInt32(int(CST1.arg) + int(CST2.arg))}], + "unresolved": [set(), + set()], + "has_loop": [False, False]} # Test graph 4 -g4_test1 = DepNodeTest(g4_ira) +G4_TEST1 = DepNodeTest(G4_IRA) -g4_test1_dn1 = DependencyNode(g4_irb2.label, a, len(g2_irb0.irs)) -g4_test1_dn2 = DependencyNode(g4_irb2.label, b, 0) -g4_test1_dn3 = DependencyNode(g4_irb0.label, b, 0) +G4_TEST1_DN1 = DependencyNode( + G4_IRB2.label, A, len(G2_IRB0.irs), next(STEP_COUNTER)) +G4_TEST1_DN2 = DependencyNode(G4_IRB2.label, B, 0, next(STEP_COUNTER)) +G4_TEST1_DN3 = DependencyNode(G4_IRB0.label, B, 0, 10) +G4_TEST1_DN4 = DependencyNode(G4_IRB0.label, G4_IRA.IRDst, 0, 0) -g4_test1.add_uniq_edge(g4_test1_dn2, g4_test1_dn1) +G4_TEST1.add_uniq_edge(G4_TEST1_DN2, G4_TEST1_DN1) -g4_input = (set([g4_test1_dn1]), set([g4_irb0.label])) +G4_INPUT = (set([G4_TEST1_DN1]), set([G4_IRB0.label])) -g4_output1 = {"graph": g4_test1, - "emul": {a: b_init}, - "unresolved": set([g4_test1_dn3]), - "has_loop": False} +G4_OUTPUT = {"graph": [G4_TEST1], + "emul": [{A: B_INIT}], + "unresolved": [set([G4_TEST1_DN3.nostep_repr])], + "has_loop": [False]} # Test graph 5 -g5_test1 = DepNodeTest(g5_ira) +G5_TEST1_0 = DepNodeTest(G5_IRA) +G5_TEST1_1 = DepNodeTest(G5_IRA) + +G5_TEST1_0_DN1 = DependencyNode( + G5_IRB2.label, A, len(G5_IRB2.irs), next(STEP_COUNTER)) +G5_TEST1_0_DN2 = DependencyNode(G5_IRB2.label, B, 0, next(STEP_COUNTER)) +G5_TEST1_0_DN3 = DependencyNode(G5_IRB1.label, B, 0, next(STEP_COUNTER)) +G5_TEST1_0_DN4 = DependencyNode(G5_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G5_TEST1_0_DN5 = DependencyNode(G5_IRB1.label, CST2, 0, next(STEP_COUNTER)) -g5_test1_dn1 = DependencyNode(g5_irb2.label, a, len(g5_irb2.irs)) -g5_test1_dn2 = DependencyNode(g5_irb2.label, b, 0) -g5_test1_dn3 = DependencyNode(g5_irb1.label, b, 0) -g5_test1_dn4 = DependencyNode(g5_irb0.label, cst1, 0) -g5_test1_dn5 = DependencyNode(g5_irb1.label, cst2, 0) +G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN4, G5_TEST1_0_DN3) +G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN3, G5_TEST1_0_DN2) +G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN5, G5_TEST1_0_DN2) +G5_TEST1_0.add_uniq_edge(G5_TEST1_0_DN2, G5_TEST1_0_DN1) -g5_test1.add_uniq_edge(g5_test1_dn4, g5_test1_dn3) -g5_test1.add_uniq_edge(g5_test1_dn3, g5_test1_dn2) -g5_test1.add_uniq_edge(g5_test1_dn5, g5_test1_dn2) -g5_test1.add_uniq_edge(g5_test1_dn2, g5_test1_dn1) +G5_TEST1_1_DN3 = DependencyNode(G5_IRB1.label, B, 0, next(STEP_COUNTER)) +G5_TEST1_1_DN5 = DependencyNode(G5_IRB1.label, CST2, 0, next(STEP_COUNTER)) -g5_input = (set([g5_test1_dn1]), set([g5_irb0.label])) +G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN4, G5_TEST1_1_DN3) +G5_TEST1_1.add_uniq_edge(G5_TEST1_1_DN3, G5_TEST1_0_DN3) +G5_TEST1_1.add_uniq_edge(G5_TEST1_1_DN5, G5_TEST1_0_DN3) +G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN3, G5_TEST1_0_DN2) +G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN5, G5_TEST1_0_DN2) +G5_TEST1_1.add_uniq_edge(G5_TEST1_0_DN2, G5_TEST1_0_DN1) -g5_output1 = {"graph": g5_test1, - "emul": {}, - "unresolved": set(), - "has_loop": True} +G5_INPUT = (set([G5_TEST1_0_DN1]), set([G5_IRB0.label])) + +G5_OUTPUT = {"graph": [G5_TEST1_0, G5_TEST1_1], + "emul": [{A: CST35}, {A: CST23}], + "unresolved": [set(), set()], + "has_loop": [True, False]} # Test graph 6 -g6_test1_0 = DepNodeTest(g6_ira) +G6_TEST1_0 = DepNodeTest(G6_IRA) -g6_test1_0_dn1 = DependencyNode(g6_irb1.label, a, len(g6_irb1.irs)) -g6_test1_0_dn2 = DependencyNode(g6_irb1.label, b, 0) -g6_test1_0_dn3 = DependencyNode(g6_irb0.label, cst1, 0) +G6_TEST1_0_DN1 = DependencyNode( + G6_IRB1.label, A, len(G6_IRB1.irs), next(STEP_COUNTER)) +G6_TEST1_0_DN2 = DependencyNode(G6_IRB1.label, B, 0, next(STEP_COUNTER)) +G6_TEST1_0_DN3 = DependencyNode(G6_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g6_test1_0.add_uniq_edge(g6_test1_0_dn3, g6_test1_0_dn2) -g6_test1_0.add_uniq_edge(g6_test1_0_dn2, g6_test1_0_dn1) +G6_TEST1_0.add_uniq_edge(G6_TEST1_0_DN3, G6_TEST1_0_DN2) +G6_TEST1_0.add_uniq_edge(G6_TEST1_0_DN2, G6_TEST1_0_DN1) -g6_input = (set([g6_test1_0_dn1]), set([g6_irb0.label])) +G6_INPUT = (set([G6_TEST1_0_DN1]), set([G6_IRB0.label])) -g6_output1 = {"graph": g6_test1_0, - "emul": {a: cst1}, - "unresolved": set(), - "has_loop": True} +G6_OUTPUT = {"graph": [G6_TEST1_0], + "emul": [{A: CST1}], + "unresolved": [set()], + "has_loop": [False]} # Test graph 7 -g7_test1_0 = DepNodeTest(g7_ira) +G7_TEST1_0 = DepNodeTest(G7_IRA) -g7_test1_0_dn1 = DependencyNode(g7_irb2.label, a, len(g7_irb2.irs)) -g7_test1_0_dn2 = DependencyNode(g7_irb1.label, b, 1) -g7_test1_0_dn3 = DependencyNode(g7_irb1.label, c, 0) -g7_test1_0_dn4 = DependencyNode(g7_irb0.label, cst1, 0) +G7_TEST1_0_DN1 = DependencyNode( + G7_IRB2.label, A, len(G7_IRB2.irs), next(STEP_COUNTER)) +G7_TEST1_0_DN2 = DependencyNode(G7_IRB1.label, B, 1, next(STEP_COUNTER)) +G7_TEST1_0_DN3 = DependencyNode(G7_IRB1.label, C, 0, next(STEP_COUNTER)) +G7_TEST1_0_DN4 = DependencyNode(G7_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g7_test1_0.add_uniq_edge(g7_test1_0_dn4, g7_test1_0_dn3) -g7_test1_0.add_uniq_edge(g7_test1_0_dn3, g7_test1_0_dn2) -g7_test1_0.add_uniq_edge(g7_test1_0_dn2, g7_test1_0_dn1) +G7_TEST1_0.add_uniq_edge(G7_TEST1_0_DN4, G7_TEST1_0_DN3) +G7_TEST1_0.add_uniq_edge(G7_TEST1_0_DN3, G7_TEST1_0_DN2) +G7_TEST1_0.add_uniq_edge(G7_TEST1_0_DN2, G7_TEST1_0_DN1) -g7_input = (set([g7_test1_0_dn1]), set([g7_irb0.label])) +G7_INPUT = (set([G7_TEST1_0_DN1]), set([G7_IRB0.label])) -g7_output1 = {"graph": g7_test1_0, - "emul": {a: cst1}, - "unresolved": set(), - "has_loop": True} +G7_OUTPUT = {"graph": [G7_TEST1_0], + "emul": [{A: CST1}], + "unresolved": [set()], + "has_loop": [False]} # Test graph 8 -g8_test1_0 = DepNodeTest(g8_ira) -g8_test1_1 = DepNodeTest(g8_ira) +G8_TEST1_0 = DepNodeTest(G8_IRA) +G8_TEST1_1 = DepNodeTest(G8_IRA) -g8_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) -g8_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0) -g8_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0) -g8_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0) +G8_TEST1_0_DN1 = DependencyNode( + G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) +G8_TEST1_0_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) +G8_TEST1_0_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) +G8_TEST1_0_DN4 = DependencyNode(G8_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g8_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) -g8_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0) -g8_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0) -g8_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1) +G8_TEST1_1_DN1 = DependencyNode( + G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) +G8_TEST1_1_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) +G8_TEST1_1_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) +G8_TEST1_1_DN4 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) -g8_test1_1_dn5 = DependencyNode(g8_irb0.label, d, 0) +G8_TEST1_1_DN5 = DependencyNode(G8_IRB0.label, D, 0, next(STEP_COUNTER)) -g8_test1_0.add_uniq_edge(g8_test1_0_dn4, g8_test1_0_dn3) -g8_test1_0.add_uniq_edge(g8_test1_0_dn3, g8_test1_0_dn2) -g8_test1_0.add_uniq_edge(g8_test1_0_dn2, g8_test1_0_dn1) +G8_TEST1_0.add_uniq_edge(G8_TEST1_0_DN4, G8_TEST1_0_DN3) +G8_TEST1_0.add_uniq_edge(G8_TEST1_0_DN3, G8_TEST1_0_DN2) +G8_TEST1_0.add_uniq_edge(G8_TEST1_0_DN2, G8_TEST1_0_DN1) -g8_test1_1.add_uniq_edge(g8_test1_1_dn4, g8_test1_1_dn3) -g8_test1_1.add_uniq_edge(g8_test1_1_dn3, g8_test1_1_dn2) -g8_test1_1.add_uniq_edge(g8_test1_1_dn2, g8_test1_1_dn1) +G8_TEST1_1.add_uniq_edge(G8_TEST1_1_DN4, G8_TEST1_1_DN3) +G8_TEST1_1.add_uniq_edge(G8_TEST1_1_DN3, G8_TEST1_1_DN2) +G8_TEST1_1.add_uniq_edge(G8_TEST1_1_DN2, G8_TEST1_1_DN1) -g8_input = (set([g8_test1_0_dn1]), set([g3_irb0.label])) +G8_INPUT = (set([G8_TEST1_0_DN1]), set([G3_IRB0.label])) -g8_output1 = {"graph": g8_test1_0, - "emul": {a: cst1}, - "unresolved": set(), - "has_loop": False} +G8_OUTPUT = {"graph": [G8_TEST1_0, G8_TEST1_1], + "emul": [{A: D_INIT}, {A: CST1}], + "unresolved": [set([G8_TEST1_1_DN5.nostep_repr]), set()], + "has_loop": [True, False]} -g8_output2 = {"graph": g8_test1_1, - "emul": {a: d_init}, - "unresolved": set([g8_test1_1_dn5]), - "has_loop": True} +# Test 9: Multi elements +G9_TEST1_0 = DepNodeTest(G8_IRA) +G9_TEST1_1 = DepNodeTest(G8_IRA) + +G9_TEST1_0_DN1 = DependencyNode( + G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) +G9_TEST1_0_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) +G9_TEST1_0_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) +G9_TEST1_0_DN4 = DependencyNode(G8_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G9_TEST1_0_DN5 = DependencyNode( + G8_IRB2.label, C, len(G8_IRB2.irs), next(STEP_COUNTER)) +G9_TEST1_0_DN6 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) + +G9_TEST1_1_DN1 = DependencyNode( + G8_IRB2.label, A, len(G8_IRB2.irs), next(STEP_COUNTER)) +G9_TEST1_1_DN2 = DependencyNode(G8_IRB2.label, B, 0, next(STEP_COUNTER)) +G9_TEST1_1_DN3 = DependencyNode(G8_IRB1.label, C, 0, next(STEP_COUNTER)) +G9_TEST1_1_DN4 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) +G9_TEST1_1_DN5 = DependencyNode( + G8_IRB2.label, C, len(G8_IRB2.irs), next(STEP_COUNTER)) +G9_TEST1_1_DN6 = DependencyNode(G8_IRB1.label, D, 1, next(STEP_COUNTER)) + + +G9_TEST1_0.add_uniq_edge(G9_TEST1_0_DN4, G9_TEST1_0_DN3) +G9_TEST1_0.add_uniq_edge(G9_TEST1_0_DN3, G9_TEST1_0_DN2) +G9_TEST1_0.add_uniq_edge(G9_TEST1_0_DN2, G9_TEST1_0_DN1) +G9_TEST1_0.add_uniq_edge(G9_TEST1_0_DN6, G9_TEST1_0_DN5) + +G9_TEST1_1.add_uniq_edge(G9_TEST1_1_DN6, G9_TEST1_1_DN5) +G9_TEST1_1.add_uniq_edge(G9_TEST1_1_DN4, G9_TEST1_1_DN3) +G9_TEST1_1.add_uniq_edge(G9_TEST1_1_DN3, G9_TEST1_1_DN2) +G9_TEST1_1.add_uniq_edge(G9_TEST1_1_DN2, G9_TEST1_1_DN1) + +G9_INPUT = (set([G9_TEST1_0_DN1, G9_TEST1_0_DN5]), set([G8_IRB0.label])) + +G9_OUTPUT = {"graph": [G9_TEST1_1, G9_TEST1_0], + "emul": [{A: D_INIT, C: D_INIT}, + {A: CST1, C: D_INIT}], + "unresolved": [set([G8_TEST1_1_DN5.nostep_repr]), + set([G8_TEST1_1_DN5.nostep_repr])], + "has_loop": [True, False]} -# Test 9: Multi elements +# Test 10: loop at beginning -g9_test1_0 = DepNodeTest(g8_ira) -g9_test1_1 = DepNodeTest(g8_ira) +G10_TEST1_0 = DepNodeTest(G10_IRA) +G10_TEST1_1 = DepNodeTest(G10_IRA) -g9_test1_0_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) -g9_test1_0_dn2 = DependencyNode(g8_irb2.label, b, 0) -g9_test1_0_dn3 = DependencyNode(g8_irb1.label, c, 0) -g9_test1_0_dn4 = DependencyNode(g8_irb0.label, cst1, 0) -g9_test1_0_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs)) -g9_test1_0_dn6 = DependencyNode(g8_irb1.label, d, 1) +G10_TEST1_0_DN1 = DependencyNode( + G10_IRB2.label, A, len(G10_IRB2.irs), next(STEP_COUNTER)) +G10_TEST1_0_DN2 = DependencyNode(G10_IRB2.label, B, 0, next(STEP_COUNTER)) +G10_TEST1_0_DN3 = DependencyNode(G10_IRB1.label, B, 0, next(STEP_COUNTER)) +G10_TEST1_0_DN4 = DependencyNode(G10_IRB1.label, CST2, 0, next(STEP_COUNTER)) -g9_test1_1_dn1 = DependencyNode(g8_irb2.label, a, len(g8_irb2.irs)) -g9_test1_1_dn2 = DependencyNode(g8_irb2.label, b, 0) -g9_test1_1_dn3 = DependencyNode(g8_irb1.label, c, 0) -g9_test1_1_dn4 = DependencyNode(g8_irb1.label, d, 1) -g9_test1_1_dn5 = DependencyNode(g8_irb2.label, c, len(g8_irb2.irs)) +G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN3, G10_TEST1_0_DN2) +G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN4, G10_TEST1_0_DN2) +G10_TEST1_0.add_uniq_edge(G10_TEST1_0_DN2, G10_TEST1_0_DN1) +G10_TEST1_1_DN3 = DependencyNode(G10_IRB1.label, B, 0, next(STEP_COUNTER)) +G10_TEST1_1_DN4 = DependencyNode(G10_IRB1.label, CST2, 0, next(STEP_COUNTER)) -g9_test1_0.add_uniq_edge(g9_test1_0_dn4, g9_test1_0_dn3) -g9_test1_0.add_uniq_edge(g9_test1_0_dn3, g9_test1_0_dn2) -g9_test1_0.add_uniq_edge(g9_test1_0_dn2, g9_test1_0_dn1) -g9_test1_0.add_uniq_edge(g9_test1_0_dn6, g9_test1_0_dn5) +G10_TEST1_1.add_uniq_edge(G10_TEST1_1_DN3, G10_TEST1_0_DN3) +G10_TEST1_1.add_uniq_edge(G10_TEST1_1_DN4, G10_TEST1_0_DN3) +G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN3, G10_TEST1_0_DN2) +G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN4, G10_TEST1_0_DN2) +G10_TEST1_1.add_uniq_edge(G10_TEST1_0_DN2, G10_TEST1_0_DN1) -g9_test1_1.add_uniq_edge(g9_test1_1_dn4, g9_test1_1_dn5) -g9_test1_1.add_uniq_edge(g9_test1_1_dn4, g9_test1_1_dn3) -g9_test1_1.add_uniq_edge(g9_test1_1_dn3, g9_test1_1_dn2) -g9_test1_1.add_uniq_edge(g9_test1_1_dn2, g9_test1_1_dn1) +G10_INPUT = (set([G10_TEST1_0_DN1]), set([G10_IRB1.label])) -g9_input = (set([g9_test1_0_dn1, g9_test1_0_dn5]), set([g8_irb0.label])) +G10_OUTPUT = {"graph": [G10_TEST1_0, G10_TEST1_1], + "emul": [{A: B_INIT + CST24}, {A: B_INIT + CST2}], + "unresolved": [set([G10_TEST1_0_DN3.nostep_repr]), + set([G10_TEST1_0_DN3.nostep_repr])], + "has_loop": [True, False]} -g9_output1 = {"graph": g9_test1_0, - "emul": {a: cst1, - c: d_init}, - "unresolved": set([g8_test1_1_dn5]), - "has_loop": False} -g9_output2 = {"graph": g9_test1_1, - "emul": {a: d_init, - c: d_init}, - "unresolved": set([g8_test1_1_dn5]), - "has_loop": True} +# Test 11: no dual bloc emulation +G11_TEST1 = DepNodeTest(G11_IRA) +G11_TEST1_DN1 = DependencyNode( + G11_IRB2.label, A, len(G11_IRB2.irs), next(STEP_COUNTER)) +G11_TEST1_DN2 = DependencyNode(G11_IRB2.label, A, 0, next(STEP_COUNTER)) +G11_TEST1_DN3 = DependencyNode(G11_IRB2.label, B, 0, next(STEP_COUNTER)) +G11_TEST1_DN4 = DependencyNode(G11_IRB1.label, A, 0, next(STEP_COUNTER)) +G11_TEST1_DN5 = DependencyNode(G11_IRB1.label, B, 0, next(STEP_COUNTER)) +G11_TEST1_DN6 = DependencyNode(G11_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G11_TEST1_DN7 = DependencyNode(G11_IRB0.label, CST2, 0, next(STEP_COUNTER)) -# Test 10: loop at beginning +G11_TEST1.add_uniq_edge(G11_TEST1_DN7, G11_TEST1_DN5) +G11_TEST1.add_uniq_edge(G11_TEST1_DN6, G11_TEST1_DN4) +G11_TEST1.add_uniq_edge(G11_TEST1_DN5, G11_TEST1_DN2) +G11_TEST1.add_uniq_edge(G11_TEST1_DN4, G11_TEST1_DN3) +G11_TEST1.add_uniq_edge(G11_TEST1_DN3, G11_TEST1_DN1) +G11_TEST1.add_uniq_edge(G11_TEST1_DN2, G11_TEST1_DN1) -g10_test1 = DepNodeTest(g10_ira) +G11_INPUT = (set([G11_TEST1_DN1]), set([G11_IRB0.label])) + +G11_OUTPUT = {"graph": [G11_TEST1], + "emul": [{A: ExprInt32(0x1)}], + "unresolved": [set()], + "has_loop": [False]} +# Test graph 12 -g10_test1_dn1 = DependencyNode(g10_irb2.label, a, len(g10_irb2.irs)) -g10_test1_dn2 = DependencyNode(g10_irb2.label, b, 0) -g10_test1_dn3 = DependencyNode(g10_irb1.label, b, 0) -g10_test1_dn4 = DependencyNode(g10_irb1.label, cst2, 0) +G12_TEST1_0 = DepNodeTest(G12_IRA) +G12_TEST1_1 = DepNodeTest(G12_IRA) -g10_test1.add_uniq_edge(g10_test1_dn3, g10_test1_dn2) -g10_test1.add_uniq_edge(g10_test1_dn4, g10_test1_dn2) -g10_test1.add_uniq_edge(g10_test1_dn2, g10_test1_dn1) +G12_TEST1_0_DN1 = DependencyNode(G12_IRB2.label, B, 1, next(STEP_COUNTER)) +G12_TEST1_0_DN2 = DependencyNode(G12_IRB2.label, A, 0, next(STEP_COUNTER)) +G12_TEST1_0_DN3 = DependencyNode(G12_IRB1.label, B, 0, next(STEP_COUNTER)) +G12_TEST1_0_DN4 = DependencyNode(G12_IRB0.label, CST1, 0, next(STEP_COUNTER)) -g10_input = (set([g10_test1_dn1]), set([g10_irb1.label])) -g10_output1 = {"graph": g10_test1, - "emul": {}, - "unresolved": set([g10_test1_dn3]), - "has_loop": True} +G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN2, G12_TEST1_0_DN1) +G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN3, G12_TEST1_0_DN2) +G12_TEST1_0.add_uniq_edge(G12_TEST1_0_DN4, G12_TEST1_0_DN3) +G12_TEST1_1_DN3 = DependencyNode(G12_IRB1.label, B, 1, next(STEP_COUNTER)) +G12_TEST1_1_DN5 = DependencyNode(G12_IRB1.label, CST2, 1, next(STEP_COUNTER)) -# Test 11: no dual bloc emulation -g11_test1 = DepNodeTest(g11_ira) +G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN4, G12_TEST1_1_DN3) +G12_TEST1_1.add_uniq_edge(G12_TEST1_1_DN5, G12_TEST1_0_DN3) +G12_TEST1_1.add_uniq_edge(G12_TEST1_1_DN3, G12_TEST1_0_DN3) +G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN3, G12_TEST1_0_DN2) +G12_TEST1_1.add_uniq_edge(G12_TEST1_0_DN2, G12_TEST1_0_DN1) + + +G12_INPUT = (set([G12_TEST1_0_DN1]), set([])) -g11_test1_dn1 = DependencyNode(g11_irb2.label, a, len(g11_irb2.irs)) -g11_test1_dn2 = DependencyNode(g11_irb2.label, a, 0) -g11_test1_dn3 = DependencyNode(g11_irb2.label, b, 0) -g11_test1_dn4 = DependencyNode(g11_irb1.label, a, 0) -g11_test1_dn5 = DependencyNode(g11_irb1.label, b, 0) -g11_test1_dn6 = DependencyNode(g11_irb0.label, cst1, 0) -g11_test1_dn7 = DependencyNode(g11_irb0.label, cst2, 0) +G12_OUTPUT = {"graph": [G12_TEST1_0, G12_TEST1_1], + "emul": [{B: CST23}, {B: CST1}], + "unresolved": [set(), set()], + "has_loop": [True, False]} -g11_test1.add_uniq_edge(g11_test1_dn7, g11_test1_dn5) -g11_test1.add_uniq_edge(g11_test1_dn6, g11_test1_dn4) -g11_test1.add_uniq_edge(g11_test1_dn5, g11_test1_dn2) -g11_test1.add_uniq_edge(g11_test1_dn4, g11_test1_dn3) -g11_test1.add_uniq_edge(g11_test1_dn3, g11_test1_dn1) -g11_test1.add_uniq_edge(g11_test1_dn2, g11_test1_dn1) +# Test graph 13: -g11_input = (set([g11_test1_dn1]), set([g11_irb0.label])) +# All filters +G13_TEST1_0 = DepNodeTest(G13_IRA) +G13_TEST1_1 = DepNodeTest(G13_IRA) -g11_output1 = {"graph": g11_test1, - "emul": {a: ExprInt32(0x1)}, - "unresolved": set(), - "has_loop": False} +G13_TEST1_0_DN1 = DependencyNode(G13_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G13_TEST1_0_DN2 = DependencyNode(G13_IRB1.label, A, 0, next(STEP_COUNTER)) +G13_TEST1_0_DN3 = DependencyNode(G13_IRB3.label, C, 0, next(STEP_COUNTER)) +G13_TEST1_0_DN4 = DependencyNode(G13_IRB3.label, R, 1, next(STEP_COUNTER)) +G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN3, G13_TEST1_0_DN4) +G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN2, G13_TEST1_0_DN3) +G13_TEST1_0.add_uniq_edge(G13_TEST1_0_DN1, G13_TEST1_0_DN2) + +G13_TEST1_1_DN5 = DependencyNode(G13_IRB2.label, A, 0, next(STEP_COUNTER)) +G13_TEST1_1_DN6 = DependencyNode(G13_IRB2.label, CST3, 0, next(STEP_COUNTER)) +G13_TEST1_1_DN7 = DependencyNode(G13_IRB2.label, B, 1, next(STEP_COUNTER)) +G13_TEST1_1_DN8 = DependencyNode(G13_IRB2.label, CST3, 1, next(STEP_COUNTER)) + +G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN3, G13_TEST1_0_DN4) +G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN2, G13_TEST1_0_DN3) + +G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN7, G13_TEST1_0_DN2) +G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN8, G13_TEST1_0_DN2) +G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN5, G13_TEST1_1_DN7) +G13_TEST1_1.add_uniq_edge(G13_TEST1_1_DN6, G13_TEST1_1_DN7) + +G13_TEST1_1.add_uniq_edge(G13_TEST1_0_DN1, G13_TEST1_1_DN5) + +# Implicit dependencies + +G13_TEST2_0 = DepNodeTest(G13_IRA) +G13_TEST2_1 = DepNodeTest(G13_IRA) + +G13_TEST2_0_DN1 = DependencyNode(G13_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G13_TEST2_0_DN2 = DependencyNode(G13_IRB1.label, A, 0, next(STEP_COUNTER)) +G13_TEST2_0_DN3 = DependencyNode(G13_IRB3.label, C, 0, next(STEP_COUNTER)) +G13_TEST2_0_DN4 = DependencyNode(G13_IRB3.label, R, 1, next(STEP_COUNTER)) +G13_TEST2_0_DN5 = DependencyNode(G13_IRB1.label, R, 1, next(STEP_COUNTER)) + +G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN3, G13_TEST2_0_DN4) +G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN2, G13_TEST2_0_DN3) +G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN1, G13_TEST2_0_DN2) +G13_TEST2_0.add_uniq_edge(G13_TEST2_0_DN5, G13_TEST2_0_DN3) + +G13_TEST2_1_DN5 = DependencyNode(G13_IRB2.label, A, 0, next(STEP_COUNTER)) +G13_TEST2_1_DN6 = DependencyNode(G13_IRB2.label, CST3, 0, next(STEP_COUNTER)) +G13_TEST2_1_DN7 = DependencyNode(G13_IRB2.label, B, 1, next(STEP_COUNTER)) +G13_TEST2_1_DN8 = DependencyNode(G13_IRB2.label, CST3, 1, next(STEP_COUNTER)) +G13_TEST2_1_DN9 = DependencyNode(G13_IRB1.label, R, 1, next(STEP_COUNTER)) + +G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN3, G13_TEST2_0_DN4) +G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN2, G13_TEST2_0_DN3) +G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN5, G13_TEST2_0_DN3) + +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN7, G13_TEST2_0_DN2) +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN8, G13_TEST2_0_DN2) +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN5, G13_TEST2_1_DN7) +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN6, G13_TEST2_1_DN7) + +G13_TEST2_1.add_uniq_edge(G13_TEST2_0_DN1, G13_TEST2_1_DN5) +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN9, G13_TEST2_0_DN5) +G13_TEST2_1.add_uniq_edge(G13_TEST2_1_DN9, G13_TEST2_1_DN5) + + +DN13_UR_R = DependencyNode(G13_IRB0.label, R, 0, 0).nostep_repr + +G13_INPUT = (set([G13_TEST1_0_DN4]), set([])) + +G13_OUTPUT = {"graph": [G13_TEST1_0, G13_TEST1_1], + "graph_implicit": [G13_TEST2_0, G13_TEST2_1], + "emul": [{R: CST37}, {R: CST1}], + "unresolved": [set(), set()], + "unresolved_implicit": [set([DN13_UR_R]), set([DN13_UR_R])], + "has_loop": [True, False]} + +# Test graph 14 + +# All filters +G14_TEST1_0 = DepNodeTest(G14_IRA) +G14_TEST1_1 = DepNodeTest(G14_IRA) + +G14_TEST1_0_DN1 = DependencyNode(G14_IRB3.label, R, 1, next(STEP_COUNTER)) +G14_TEST1_0_DN2 = DependencyNode(G14_IRB3.label, D, 0, next(STEP_COUNTER)) +G14_TEST1_0_DN3 = DependencyNode(G14_IRB3.label, B, 0, next(STEP_COUNTER)) +G14_TEST1_0_DN4 = DependencyNode(G14_IRB1.label, A, 0, next(STEP_COUNTER)) +G14_TEST1_0_DN5 = DependencyNode(G14_IRB0.label, CST1, 0, next(STEP_COUNTER)) + +G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) +G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) + +G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) +G14_TEST1_0.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_0_DN4) + +G14_TEST1_1_DN5 = DependencyNode(G14_IRB2.label, D, 1, next(STEP_COUNTER)) +G14_TEST1_1_DN6 = DependencyNode(G14_IRB2.label, CST1, 1, next(STEP_COUNTER)) +G14_TEST1_1_DN7 = DependencyNode(G14_IRB2.label, A, 0, next(STEP_COUNTER)) +G14_TEST1_1_DN8 = DependencyNode( + G14_IRB2.label, A, 0, next(STEP_COUNTER) + 1) +G14_TEST1_1_DN9 = DependencyNode( + G14_IRB0.label, CST1, 0, next(STEP_COUNTER) + 1) + +# 1 loop +G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) +G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) + +G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) +G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN5, G14_TEST1_0_DN4) +G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN6, G14_TEST1_0_DN4) +G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_1_DN5) +G14_TEST1_1.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_1_DN7) + +G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN8, G14_TEST1_0_DN2) +G14_TEST1_1.add_uniq_edge(G14_TEST1_1_DN9, G14_TEST1_1_DN8) + +# Implicit dependencies +G14_TEST2_0 = DepNodeTest(G14_IRA) +G14_TEST2_1 = DepNodeTest(G14_IRA) + +G14_TEST2_0_DN6 = DependencyNode(G14_IRB1.label, C, 1, next(STEP_COUNTER)) + +G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) +G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) + +G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) +G14_TEST2_0.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_0_DN4) + +G14_TEST2_0.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN3) +G14_TEST2_0.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN2) + +# 1 loop +G14_TEST2_0_DN7 = DependencyNode(G14_IRB1.label, C, 1, next(STEP_COUNTER)) + +G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN2, G14_TEST1_0_DN1) +G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN3, G14_TEST1_0_DN1) + +G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN4, G14_TEST1_0_DN3) +G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN5, G14_TEST1_0_DN4) +G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN6, G14_TEST1_0_DN4) +G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN7, G14_TEST1_1_DN5) +G14_TEST2_1.add_uniq_edge(G14_TEST1_0_DN5, G14_TEST1_1_DN7) + +G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN8, G14_TEST1_0_DN2) +G14_TEST2_1.add_uniq_edge(G14_TEST1_1_DN9, G14_TEST1_1_DN8) + +G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN3) +G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN6, G14_TEST1_0_DN2) + +G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN7, G14_TEST2_0_DN6) +G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN7, G14_TEST1_1_DN7) +G14_TEST2_1.add_uniq_edge(G14_TEST2_0_DN7, G14_TEST1_1_DN8) + + +DN14_UR_D = DependencyNode(G14_IRB0.label, D, 0, 0).nostep_repr +DN14_UR_C = DependencyNode(G14_IRB0.label, C, 0, 0).nostep_repr + +G14_INPUT = (set([G14_TEST1_0_DN1]), set([])) + +G14_OUTPUT = {"graph": [G14_TEST1_0, G14_TEST1_1], + "graph_implicit": [G14_TEST2_0, G14_TEST2_1], + "emul": [{R: CST33}, {R: D_INIT + CST1}], + "unresolved": [set(), set([DN14_UR_D])], + "unresolved_implicit": [set([DN14_UR_C]), + set([DN14_UR_D, DN14_UR_C])], + "has_loop": [True, False]} + +# Test graph 15 + +G15_TEST1_0 = DepNodeTest(G15_IRA) +G15_TEST1_1 = DepNodeTest(G15_IRA) + +G15_TEST1_0_DN1 = DependencyNode(G15_IRB2.label, R, 1, next(STEP_COUNTER)) +G15_TEST1_0_DN2 = DependencyNode(G15_IRB2.label, B, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN3 = DependencyNode(G15_IRB1.label, C, 2, next(STEP_COUNTER)) +G15_TEST1_0_DN4 = DependencyNode(G15_IRB1.label, D, 1, next(STEP_COUNTER)) +G15_TEST1_0_DN5 = DependencyNode(G15_IRB1.label, B, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN6 = DependencyNode(G15_IRB1.label, A, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN7 = DependencyNode(G15_IRB0.label, CST1, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN8 = DependencyNode(G15_IRB1.label, C, 2, next(STEP_COUNTER)) +G15_TEST1_0_DN9 = DependencyNode(G15_IRB1.label, D, 1, next(STEP_COUNTER)) +G15_TEST1_0_DN10 = DependencyNode(G15_IRB1.label, A, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN11 = DependencyNode(G15_IRB1.label, B, 0, next(STEP_COUNTER)) +G15_TEST1_0_DN12 = DependencyNode( + G15_IRB0.label, CST1, 0, next(STEP_COUNTER)) + + +# 1 loop +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN2, G15_TEST1_0_DN1) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN3, G15_TEST1_0_DN2) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN4, G15_TEST1_0_DN3) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN5, G15_TEST1_0_DN4) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN6, G15_TEST1_0_DN4) + +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN7, G15_TEST1_0_DN6) + +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN8, G15_TEST1_0_DN5) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN9, G15_TEST1_0_DN8) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN10, G15_TEST1_0_DN9) +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN11, G15_TEST1_0_DN9) + +G15_TEST1_0.add_uniq_edge(G15_TEST1_0_DN12, G15_TEST1_0_DN10) + + +# 0 loop + +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN2, G15_TEST1_0_DN1) +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN3, G15_TEST1_0_DN2) +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN4, G15_TEST1_0_DN3) +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN5, G15_TEST1_0_DN4) +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN6, G15_TEST1_0_DN4) +G15_TEST1_1.add_uniq_edge(G15_TEST1_0_DN7, G15_TEST1_0_DN6) + +G15_INPUT = (set([G15_TEST1_0_DN1]), set([])) + +DN15_UNRESOLVED = DependencyNode(G15_IRB0.label, B, 0, 0).nostep_repr +G15_OUTPUT = {"graph": [G15_TEST1_0, G15_TEST1_1], + "emul": [{R: B_INIT + CST22}, {R: B_INIT + CST1}], + "unresolved": [set([DN15_UNRESOLVED]), set([DN15_UNRESOLVED])], + "has_loop": [True, False]} + +# Test graph 16 +G16_TEST1_0_DN1 = DependencyNode(G16_IRB5.label, R, 1, next(STEP_COUNTER)) +G16_TEST1_0_DN2 = DependencyNode(G16_IRB5.label, A, 0, next(STEP_COUNTER)) +G16_TEST1_0_DN3 = DependencyNode(G16_IRB0.label, CST1, 0, next(STEP_COUNTER)) + +G16_TEST1_0 = DepNodeTest(G16_IRA) + +G16_TEST1_0.add_uniq_edge(G16_TEST1_0_DN3, G16_TEST1_0_DN2) +G16_TEST1_0.add_uniq_edge(G16_TEST1_0_DN2, G16_TEST1_0_DN1) + +G16_INPUT = (set([G16_TEST1_0_DN1]), set([])) + +G16_OUTPUT = {"graph": [G16_TEST1_0], + "emul": [{R: CST1}], + "unresolved": [set()], + "has_loop": [False]} + +FAILED = set() # Launch tests -for i, test in enumerate([(g1_ira, g1_input, [g1_output1]), - (g2_ira, g2_input, [g2_output1]), - (g3_ira, g3_input, [g3_output1, g3_output2]), - (g4_ira, g4_input, [g4_output1]), - (g5_ira, g5_input, [g5_output1]), - (g6_ira, g6_input, [g6_output1]), - (g7_ira, g7_input, [g7_output1]), - (g8_ira, g8_input, [g8_output1, g8_output2]), - (g8_ira, g9_input, [g9_output1, g9_output2]), - (g10_ira, g10_input, [g10_output1]), - (g11_ira, g11_input, [g11_output1]), - ]): +for test_nb, test in enumerate([(G1_IRA, G1_INPUT, G1_OUTPUT), + (G2_IRA, G2_INPUT, G2_OUTPUT), + (G3_IRA, G3_INPUT, G3_OUTPUT), + (G4_IRA, G4_INPUT, G4_OUTPUT), + (G5_IRA, G5_INPUT, G5_OUTPUT), + (G6_IRA, G6_INPUT, G6_OUTPUT), + (G7_IRA, G7_INPUT, G7_OUTPUT), + (G8_IRA, G8_INPUT, G8_OUTPUT), + (G8_IRA, G9_INPUT, G9_OUTPUT), + (G10_IRA, G10_INPUT, G10_OUTPUT), + (G11_IRA, G11_INPUT, G11_OUTPUT), + (G12_IRA, G12_INPUT, G12_OUTPUT), + (G13_IRA, G13_INPUT, G13_OUTPUT), + (G14_IRA, G14_INPUT, G14_OUTPUT), + (G15_IRA, G15_INPUT, G15_OUTPUT), + (G16_IRA, G16_INPUT, G16_OUTPUT), + ]): # Extract test elements - print "[+] Test", i+1 - g_ira, (depnodes, heads), g_test_list = test - open("graph_%02d.dot" % (i+1), "w").write(g_ira.g.dot()) + print "[+] Test", test_nb + 1 + g_ira, (depnodes, heads), g_test_output = test + + open("graph_%02d.dot" % (test_nb + 1), "w").write(g_ira.g.dot()) + + # Different options + suffix_key_list = ["", "_nosimp", "_nomem", "_nocall", + "_implicit"] # Test classes - for g_dep in [DependencyGraph(g_ira), - DependencyGraph(g_ira, apply_simp=False), - DependencyGraph(g_ira, follow_mem=False), - DependencyGraph(g_ira, follow_mem=False, follow_call=False)]: - print " - Class %s" % g_dep.__class__.__name__ - - ## Test public APIs - for api_i, g_list in enumerate([g_dep.get_fromDepNodes(depnodes, heads), - g_dep.get(list(depnodes)[0].label, - [depnode.element for - depnode in depnodes], - list(depnodes)[0].line_nb, - heads)]): - print " - - API %s" % ("get_fromDepNodes" if api_i == 0 else "get") - - ### Expand result iterator + for g_ind, g_dep in enumerate([DependencyGraph(g_ira), + DependencyGraph(g_ira, apply_simp=False), + DependencyGraph(g_ira, follow_mem=False), + DependencyGraph(g_ira, follow_mem=False, + follow_call=False), + DependencyGraph(g_ira, implicit=True), + ]): + print " - Class %s - %s" % (g_dep.__class__.__name__, + suffix_key_list[g_ind]) + + # Select the correct result key + mode_suffix = suffix_key_list[g_ind] + graph_test_key = "graph" + mode_suffix + if not g_test_output.has_key(graph_test_key): + graph_test_key = "graph" + + expected_results = g_test_output[graph_test_key] + + # Test public APIs + for api_i, g_list in enumerate( + [g_dep.get_from_depnodes(depnodes, heads), + g_dep.get(list(depnodes)[0].label, + [depnode.element for + depnode in depnodes], + list(depnodes)[0].line_nb, + heads) + ]): + print " - - API %s" % ("get_from_depnodes" + if api_i == 0 else "get") + + # Expand result iterator g_list = list(g_list) - ### Dump outputs graphs for debug means - for j, result in enumerate(g_list): - open("graph_test_%02d_%02d.dot" % (i + 1, j), - "w").write(result.graph.dot()) - - ### The number of results should be the same - print " - - - number of results" - assert(len(g_list) == len(g_test_list)) - - ### Match the right result (unordered) - for j, result in enumerate(g_list): - print " - - - result %d" % j - found = False - for expected in g_test_list: - if expected["graph"].__eq__(result.graph): - found = True - break - assert(found) - - #### @expected is the corresponding result, test for properties - print " - - - - emul" - if not expected["has_loop"]: - assert(expected["emul"] == result.emul()) - for element in ["unresolved"]: # TODO: has_loop - print " - - - - %s" % element - assert(expected[element] == getattr(result, element)) + + # Dump outputs graphs for debug means + for result_nb, result_graph in enumerate(g_list): + open("graph_test_%02d_%02d.dot" % (test_nb + 1, result_nb), + "w").write(result_graph.graph.dot()) + + try: + # The number of results should be the same + print " - - - number of results %d/%d" % (len(g_list), + len(expected_results)) + + error = 'len:' + \ + str(len(g_list)) + '/' + str(len(expected_results)) + assert len(g_list) == len(expected_results) + + # Check that every result appears in expected_results + for j, result in enumerate(g_list): + print " - - - result %d" % j + found = False + for expected in expected_results: + if expected.__eq__(result.graph): + found = True + error = "found1" + assert found + + # Check that every expected result appears in real results + for j, expected in enumerate(expected_results): + print " - - - expected %d" % j + found = False + for result in g_list: + if expected.__eq__(result.graph): + found = True + error = "found2" + assert found + + # Test emulation results and other properties + unresolved_test_key = "unresolved" + mode_suffix + if not g_test_output.has_key(unresolved_test_key): + unresolved_test_key = "unresolved" + + # Check that every computed result was expected + for emul_nb, result in enumerate(g_list): + print " - - - - emul %d" % emul_nb + emul_result = result.emul() + + error = "emul" + found = False + for exp_nb in xrange(len(g_list)): + if (emul_result == g_test_output["emul"][exp_nb] and + getattr(result, "unresolved") == + g_test_output[unresolved_test_key][exp_nb] and + g_test_output["has_loop"][exp_nb] == + getattr(result, "has_loop") + ): + found = True + break + assert found + + # Check that every expected result has been computed + for exp_nb in xrange(len(g_list)): + print " - - - - emul %d" % exp_nb + + error = "emul2" + found = False + for emul_nb, result in enumerate(g_list): + emul_result = result.emul() + if (emul_result == g_test_output["emul"][exp_nb] and + getattr(result, "unresolved") == + g_test_output[unresolved_test_key][exp_nb] and + g_test_output["has_loop"][exp_nb] == + getattr(result, "has_loop") + ): + found = True + break + assert found + + except AssertionError: + FAILED.add((test_nb + 1, error)) + continue + +if FAILED: + print "FAILED :", len(FAILED) + for i in sorted(FAILED, key=lambda (u, _): u): + print i, +else: + print "SUCCESS" diff --git a/test/test_all.py b/test/test_all.py index 55e69e70..b5dc0abf 100644 --- a/test/test_all.py +++ b/test/test_all.py @@ -135,22 +135,21 @@ for script in ["win_api_x86_32.py", ## Analysis testset += RegressionTest(["depgraph.py"], base_dir="analysis", - products=["graph_test_01_00.dot", - "graph_test_02_00.dot", - "graph_test_03_00.dot", - "graph_test_03_01.dot", - "graph_test_04_00.dot", - "graph_test_05_00.dot", - "graph_test_06_00.dot", - "graph_test_07_00.dot", - "graph_test_08_00.dot", - "graph_test_08_01.dot", - "graph_test_09_00.dot", - "graph_test_09_01.dot", - "graph_test_10_00.dot", - "graph_test_11_00.dot", - ] + ["graph_%02d.dot" % test_nb - for test_nb in xrange(1, 12)]) + products=[fname for fnames in ( + ["graph_test_%02d_00.dot" % test_nb, + "graph_%02d.dot" % test_nb] + for test_nb in xrange(1, 17)) + for fname in fnames] + + ["graph_test_03_01.dot", + "graph_test_05_01.dot", + "graph_test_08_01.dot", + "graph_test_09_01.dot", + "graph_test_10_01.dot", + "graph_test_12_01.dot", + "graph_test_13_01.dot", + "graph_test_14_01.dot", + "graph_test_15_01.dot" + ]) # Examples class Example(Test): |