1from itertools import count 2import logging 3 4import networkx 5 6import ailment 7from claripy.utils.orderedset import OrderedSet 8 9from ...utils.graph import dfs_back_edges, subgraph_between_nodes, dominates, shallow_reverse 10from .. import Analysis, register_analysis 11from .utils import replace_last_statement 12from .structurer_nodes import MultiNode, ConditionNode 13from .graph_region import GraphRegion 14from .condition_processor import ConditionProcessor 15 16l = logging.getLogger(name=__name__) 17 18 19# an ever-incrementing counter 20CONDITIONNODE_ADDR = count(0xff000000) 21 22 23class RegionIdentifier(Analysis): 24 """ 25 Identifies regions within a function. 26 """ 27 def __init__(self, func, cond_proc=None, graph=None): 28 self.function = func 29 self.cond_proc = cond_proc if cond_proc is not None else ConditionProcessor() 30 self._graph = graph if graph is not None else self.function.graph 31 32 self.region = None 33 self._start_node = None 34 self._loop_headers = None 35 36 self._analyze() 37 38 @staticmethod 39 def slice_graph(graph, node, frontier, include_frontier=False): 40 """ 41 Generate a slice of the graph from the head node to the given frontier. 42 43 :param networkx.DiGraph graph: The graph to work on. 44 :param node: The starting node in the graph. 45 :param frontier: A list of frontier nodes. 46 :param bool include_frontier: Whether the frontier nodes are included in the slice or not. 47 :return: A subgraph. 48 :rtype: networkx.DiGraph 49 """ 50 51 subgraph = subgraph_between_nodes(graph, node, frontier, include_frontier=include_frontier) 52 if not list(subgraph.nodes): 53 # HACK: FIXME: for infinite loop nodes, this would return an empty set, so we include the loop body itself 54 # Make sure this makes sense (EDG thinks it does) 55 if (node, node) in graph.edges: 56 subgraph.add_edge(node, node) 57 return subgraph 58 59 def _analyze(self): 60 61 # make a copy of the graph 62 graph = networkx.DiGraph(self._graph) 63 64 # preprocess: make it a super graph 65 self._make_supergraph(graph) 66 67 self._start_node = self._get_start_node(graph) 68 69 # preprocess: find loop headers 70 self._loop_headers = self._find_loop_headers(graph) 71 72 self.region = self._make_regions(graph) 73 74 @staticmethod 75 def _get_start_node(graph): 76 try: 77 return next(n for n in graph.nodes() if graph.in_degree(n) == 0) 78 except StopIteration: 79 return None 80 81 def _test_reducibility(self): 82 83 # make a copy of the graph 84 graph = networkx.DiGraph(self._graph) 85 86 # preprocess: make it a super graph 87 self._make_supergraph(graph) 88 89 while True: 90 91 changed = False 92 93 # find a node with a back-edge, remove the edge (deleting the loop), and replace it with a MultiNode 94 changed |= self._remove_self_loop(graph) 95 96 # find a node that has only one predecessor, and merge it with its predecessor (replace them with a 97 # MultiNode) 98 changed |= self._merge_single_entry_node(graph) 99 100 if not changed: 101 # a fixed-point is reached 102 break 103 104 def _make_supergraph(self, graph): 105 106 while True: 107 for src, dst, data in graph.edges(data=True): 108 type_ = data.get('type', None) 109 if type_ == 'fake_return': 110 if len(list(graph.successors(src))) == 1 and len(list(graph.predecessors(dst))) == 1: 111 self._merge_nodes(graph, src, dst, force_multinode=True) 112 break 113 elif type_ == 'call': 114 graph.remove_node(dst) 115 break 116 else: 117 break 118 119 def _find_loop_headers(self, graph): 120 return OrderedSet(sorted((t for _,t in dfs_back_edges(graph, self._start_node)), key=lambda x: x.addr)) 121 122 def _find_initial_loop_nodes(self, graph, head): 123 # TODO optimize 124 latching_nodes = { s for s,t in dfs_back_edges(graph, self._start_node) if t == head } 125 loop_subgraph = self.slice_graph(graph, head, latching_nodes, include_frontier=True) 126 nodes = set(loop_subgraph.nodes()) 127 return nodes 128 129 def _refine_loop(self, graph, head, initial_loop_nodes, initial_exit_nodes): 130 refined_loop_nodes = initial_loop_nodes.copy() 131 refined_exit_nodes = initial_exit_nodes.copy() 132 133 idom = networkx.immediate_dominators(graph, self._start_node) 134 135 new_exit_nodes = refined_exit_nodes 136 while len(refined_exit_nodes) > 1 and new_exit_nodes: 137 new_exit_nodes = set() 138 for n in list(refined_exit_nodes): 139 if all(pred in refined_loop_nodes for pred in graph.predecessors(n)) and dominates(idom, head, n): 140 refined_loop_nodes.add(n) 141 refined_exit_nodes.remove(n) 142 for u in (set(graph.successors(n)) - refined_loop_nodes): 143 new_exit_nodes.add(u) 144 refined_exit_nodes |= new_exit_nodes 145 146 refined_loop_nodes = refined_loop_nodes - refined_exit_nodes 147 148 return refined_loop_nodes, refined_exit_nodes 149 150 def _remove_self_loop(self, graph): 151 152 r = False 153 154 while True: 155 for node in graph.nodes(): 156 if node in graph[node]: 157 # found a self loop 158 self._remove_node(graph, node) 159 r = True 160 break 161 else: 162 break 163 164 return r 165 166 def _merge_single_entry_node(self, graph): 167 168 r = False 169 170 while True: 171 for node in networkx.dfs_postorder_nodes(graph): 172 preds = graph.predecessors(node) 173 if len(preds) == 1: 174 # merge the two nodes 175 self._absorb_node(graph, preds[0], node) 176 r = True 177 break 178 else: 179 break 180 181 return r 182 183 def _make_regions(self, graph): 184 185 structured_loop_headers = set() 186 new_regions = [ ] 187 188 # FIXME: _get_start_node() will fail if the graph is just a loop 189 190 # Find all loops 191 while True: 192 restart = False 193 194 self._start_node = self._get_start_node(graph) 195 196 # Start from loops 197 for node in self._loop_headers: 198 if node in structured_loop_headers: 199 continue 200 region = self._make_cyclic_region(node, graph) 201 if region is not None: 202 l.debug("Structured a loop region %r.", region) 203 new_regions.append(region) 204 structured_loop_headers.add(node) 205 restart = True 206 break 207 208 if restart: 209 continue 210 211 break 212 213 new_regions.append(GraphRegion(self._get_start_node(graph), graph, None, None, False)) 214 215 l.debug("Identified %d loop regions.", len(structured_loop_headers)) 216 l.debug("No more loops left. Start structuring acyclic regions.") 217 # No more loops left. Structure acyclic regions. 218 while new_regions: 219 region = new_regions.pop(0) 220 head = region.head 221 subgraph = region.graph 222 223 failed_region_attempts = set() 224 while self._make_acyclic_region(head, subgraph, region.graph_with_successors, failed_region_attempts, 225 region.cyclic): 226 if head not in subgraph: 227 # update head 228 head = next(iter(n for n in subgraph.nodes() if n.addr == head.addr)) 229 230 head = next(iter(n for n in subgraph.nodes() if n.addr == head.addr)) 231 region.head = head 232 233 if len(graph.nodes()) == 1 and isinstance(list(graph.nodes())[0], GraphRegion): 234 return list(graph.nodes())[0] 235 # create a large graph region 236 new_head = self._get_start_node(graph) 237 region = GraphRegion(new_head, graph, None, None, False) 238 return region 239 240 # 241 # Cyclic regions 242 # 243 244 def _make_cyclic_region(self, head, graph): 245 246 l.debug("Found cyclic region at %#08x", head.addr) 247 initial_loop_nodes = self._find_initial_loop_nodes(graph, head) 248 l.debug("Initial loop nodes %s", self._dbg_block_list(initial_loop_nodes)) 249 250 # Make sure there is no other loop contained in the current loop 251 if {n for n in initial_loop_nodes if n.addr != head.addr}.intersection(self._loop_headers): 252 return None 253 254 normal_entries = {n for n in graph.predecessors(head) if n not in initial_loop_nodes} 255 abnormal_entries = set() 256 for n in initial_loop_nodes: 257 if n == head: 258 continue 259 preds = set(graph.predecessors(n)) 260 abnormal_entries |= (preds - initial_loop_nodes) 261 l.debug("Normal entries %s", self._dbg_block_list(normal_entries)) 262 l.debug("Abnormal entries %s", self._dbg_block_list(abnormal_entries)) 263 264 initial_exit_nodes = set() 265 for n in initial_loop_nodes: 266 succs = set(graph.successors(n)) 267 initial_exit_nodes |= (succs - initial_loop_nodes) 268 269 l.debug("Initial exit nodes %s", self._dbg_block_list(initial_exit_nodes)) 270 271 refined_loop_nodes, refined_exit_nodes = self._refine_loop(graph, head, initial_loop_nodes, 272 initial_exit_nodes) 273 l.debug("Refined loop nodes %s", self._dbg_block_list(refined_loop_nodes)) 274 l.debug("Refined exit nodes %s", self._dbg_block_list(refined_exit_nodes)) 275 276 if len(refined_exit_nodes) > 1: 277 # self._get_start_node(graph) 278 node_post_order = list(networkx.dfs_postorder_nodes(graph, head)) 279 sorted_exit_nodes = sorted(list(refined_exit_nodes), key=node_post_order.index) 280 normal_exit_node = sorted_exit_nodes[0] 281 abnormal_exit_nodes = set(sorted_exit_nodes[1:]) 282 else: 283 normal_exit_node = next(iter(refined_exit_nodes)) if len(refined_exit_nodes) > 0 else None 284 abnormal_exit_nodes = set() 285 286 region = self._abstract_cyclic_region(graph, refined_loop_nodes, head, normal_entries, abnormal_entries, 287 normal_exit_node, abnormal_exit_nodes) 288 if len(region.successors) > 1: 289 # multi-successor region. refinement is required 290 self._refine_loop_successors(region, graph) 291 292 return region 293 294 def _refine_loop_successors(self, region, graph): 295 """ 296 If there are multiple successors of a loop, convert them into conditional gotos. Eventually there should be 297 only one loop successor. 298 299 :param GraphRegion region: The cyclic region to refine. 300 :param networkx.DiGraph graph: The current graph that is being structured. 301 :return: None 302 """ 303 if len(region.successors) <= 1: 304 return 305 306 # recover reaching conditions 307 self.cond_proc.recover_reaching_conditions(region, with_successors=True) 308 309 successors = list(region.successors) 310 311 condnode_addr = next(CONDITIONNODE_ADDR) 312 # create a new successor 313 cond = ConditionNode( 314 condnode_addr, 315 None, 316 self.cond_proc.reaching_conditions[successors[0]], 317 successors[0], 318 false_node=None, 319 ) 320 for succ in successors[1:]: 321 cond = ConditionNode(condnode_addr, 322 None, 323 self.cond_proc.reaching_conditions[succ], 324 succ, 325 false_node=cond, 326 ) 327 328 g = region.graph_with_successors 329 330 # modify region in place 331 region.successors = {cond} 332 for succ in successors: 333 for src, _, data in list(g.in_edges(succ, data=True)): 334 removed_edges = [ ] 335 for src2src, _, data_ in list(g.in_edges(src, data=True)): 336 removed_edges.append((src2src, src, data_)) 337 g.remove_edge(src2src, src) 338 g.remove_edge(src, succ) 339 340 # TODO: rewrite the conditional jumps in src so that it goes to cond-node instead. 341 342 # modify the last statement of src so that it jumps to cond 343 replaced_any_stmt = False 344 last_stmts = self.cond_proc.get_last_statements(src) 345 for last_stmt in last_stmts: 346 if isinstance(last_stmt, ailment.Stmt.ConditionalJump): 347 if last_stmt.true_target.value == succ.addr: 348 new_last_stmt = ailment.Stmt.ConditionalJump( 349 last_stmt.idx, 350 last_stmt.condition, 351 ailment.Expr.Const(None, None, condnode_addr, self.project.arch.bits), 352 last_stmt.false_target, 353 ins_addr=last_stmt.ins_addr, 354 ) 355 elif last_stmt.false_target.value == succ.addr: 356 new_last_stmt = ailment.Stmt.ConditionalJump( 357 last_stmt.idx, 358 last_stmt.condition, 359 last_stmt.true_target, 360 ailment.Expr.Const(None, None, condnode_addr, self.project.arch.bits), 361 ins_addr=last_stmt.ins_addr, 362 ) 363 else: 364 # none of the two branches is jumping out of the loop 365 continue 366 else: 367 new_last_stmt = ailment.Stmt.Jump( 368 last_stmt.idx, 369 ailment.Expr.Const(None, None, condnode_addr, self.project.arch.bits), 370 ins_addr=last_stmt.ins_addr, 371 ) 372 replace_last_statement(src, last_stmt, new_last_stmt) 373 replaced_any_stmt = True 374 if not replaced_any_stmt: 375 l.warning("No statement was replaced. Is there anything wrong?") 376 raise Exception() 377 378 # add src back 379 for src2src, _, data_ in removed_edges: 380 g.add_edge(src2src, src, **data_) 381 382 g.add_edge(src, cond, **data) 383 384 # modify graph 385 graph.add_edge(region, cond) 386 for succ in successors: 387 edge_data = graph.get_edge_data(region, succ) 388 graph.remove_edge(region, succ) 389 graph.add_edge(cond, succ, **edge_data) 390 391 # 392 # Acyclic regions 393 # 394 395 def _make_acyclic_region(self, head, graph, secondary_graph, failed_region_attempts, cyclic): 396 # pre-processing 397 398 # we need to create a copy of the original graph if 399 # - there are in edges to the head node, or 400 # - there are more than one end nodes 401 402 head_inedges = list(graph.in_edges(head)) 403 if head_inedges: 404 # we need a copy of the graph to remove edges coming into the head 405 graph_copy = networkx.DiGraph(graph) 406 # remove any in-edge to the head node 407 for src, _ in head_inedges: 408 graph_copy.remove_edge(src, head) 409 else: 410 graph_copy = graph 411 412 endnodes = [node for node in graph_copy.nodes() if graph_copy.out_degree(node) == 0] 413 if len(endnodes) == 0: 414 # sanity check: there should be at least one end node 415 l.critical("No end node is found in a supposedly acyclic graph. Is it really acyclic?") 416 return False 417 418 if len(endnodes) > 1: 419 # we need a copy of the graph! 420 graph_copy = networkx.DiGraph(graph_copy) 421 422 # if this graph has multiple end nodes: create a single end node 423 dummy_endnode = None 424 if len(endnodes) > 1: 425 dummy_endnode = "DUMMY_ENDNODE" 426 for endnode in endnodes: 427 graph_copy.add_edge(endnode, dummy_endnode) 428 endnodes = [ dummy_endnode ] 429 else: 430 dummy_endnode = None 431 432 # compute dominator tree 433 doms = networkx.immediate_dominators(graph_copy, head) 434 435 # compute post-dominator tree 436 inverted_graph = shallow_reverse(graph_copy) 437 postdoms = networkx.immediate_dominators(inverted_graph, endnodes[0]) 438 439 # dominance frontiers 440 df = networkx.algorithms.dominance_frontiers(graph_copy, head) 441 442 # visit the nodes in post-order 443 for node in networkx.dfs_postorder_nodes(graph_copy, source=head): 444 if node is dummy_endnode: 445 # skip the dummy endnode 446 continue 447 if cyclic and node is head: 448 continue 449 450 out_degree = graph_copy.out_degree[node] 451 if out_degree == 0: 452 # the root element of the region hierarchy should always be a GraphRegion, 453 # so we transform it into one, if necessary 454 if graph_copy.in_degree(node) == 0 and not isinstance(node, GraphRegion): 455 subgraph = networkx.DiGraph() 456 subgraph.add_node(node) 457 self._abstract_acyclic_region(graph, GraphRegion(node, subgraph, None, None, False), [], 458 secondary_graph=secondary_graph) 459 continue 460 461 # test if this node is an entry to a single-entry, single-successor region 462 levels = 0 463 postdom_node = postdoms.get(node, None) 464 while postdom_node is not None: 465 if (node, postdom_node) not in failed_region_attempts: 466 if self._check_region(graph_copy, node, postdom_node, doms, df): 467 frontier = [ postdom_node ] 468 region = self._compute_region(graph_copy, node, frontier, dummy_endnode=dummy_endnode) 469 if region is not None: 470 # l.debug("Walked back %d levels in postdom tree.", levels) 471 l.debug("Node %r, frontier %r.", node, frontier) 472 # l.debug("Identified an acyclic region %s.", self._dbg_block_list(region.graph.nodes())) 473 self._abstract_acyclic_region(graph, region, frontier, dummy_endnode=dummy_endnode, 474 secondary_graph=secondary_graph) 475 # assert dummy_endnode not in graph 476 return True 477 478 failed_region_attempts.add((node, postdom_node)) 479 if not dominates(doms, node, postdom_node): 480 break 481 if postdom_node is postdoms.get(postdom_node, None): 482 break 483 postdom_node = postdoms.get(postdom_node, None) 484 levels += 1 485 # l.debug("Walked back %d levels in postdom tree and did not find anything for %r. Next.", levels, node) 486 487 return False 488 489 @staticmethod 490 def _check_region(graph, start_node, end_node, doms, df): 491 """ 492 493 :param graph: 494 :param start_node: 495 :param end_node: 496 :param doms: 497 :param df: 498 :return: 499 """ 500 501 # if the exit node is the header of a loop that contains the start node, the dominance frontier should only 502 # contain the exit node. 503 if not dominates(doms, start_node, end_node): 504 frontier = df.get(start_node, set()) 505 for node in frontier: 506 if node is not start_node and node is not end_node: 507 return False 508 509 # no edges should enter the region. 510 for node in df.get(end_node, set()): 511 if dominates(doms, start_node, node) and node is not end_node: 512 return False 513 514 # no edges should leave the region. 515 for node in df.get(start_node, set()): 516 if node is start_node or node is end_node: 517 continue 518 if node not in df.get(end_node, set()): 519 return False 520 for pred in graph.predecessors(node): 521 if dominates(doms, start_node, pred) and not dominates(doms, end_node, pred): 522 return False 523 524 return True 525 526 @staticmethod 527 def _compute_region(graph, node, frontier, include_frontier=False, dummy_endnode=None): 528 529 subgraph = networkx.DiGraph() 530 frontier_edges = [ ] 531 queue = [ node ] 532 traversed = set() 533 534 while queue: 535 node_ = queue.pop() 536 if node_ in frontier: 537 continue 538 traversed.add(node_) 539 subgraph.add_node(node_) 540 541 for succ in graph.successors(node_): 542 edge_data = graph.get_edge_data(node_, succ) 543 544 if node_ in frontier and succ in traversed: 545 if include_frontier: 546 # if frontier nodes are included, do not keep traversing their successors 547 # however, if it has an edge to an already traversed node, we should add that edge 548 subgraph.add_edge(node_, succ, **edge_data) 549 else: 550 frontier_edges.append((node_, succ, edge_data)) 551 continue 552 553 if succ is dummy_endnode: 554 continue 555 556 if succ in frontier: 557 if not include_frontier: 558 # skip all frontier nodes 559 frontier_edges.append((node_, succ, edge_data)) 560 continue 561 subgraph.add_edge(node_, succ, **edge_data) 562 if succ in traversed: 563 continue 564 queue.append(succ) 565 566 if dummy_endnode is not None: 567 frontier = { n for n in frontier if n is not dummy_endnode } 568 569 if subgraph.number_of_nodes() > 1: 570 subgraph_with_frontier = networkx.DiGraph(subgraph) 571 for src, dst, edge_data in frontier_edges: 572 if dst is not dummy_endnode: 573 subgraph_with_frontier.add_edge(src, dst, **edge_data) 574 # assert dummy_endnode not in frontier 575 # assert dummy_endnode not in subgraph_with_frontier 576 return GraphRegion(node, subgraph, frontier, subgraph_with_frontier, False) 577 else: 578 return None 579 580 def _abstract_acyclic_region(self, graph, region, frontier, dummy_endnode=None, secondary_graph=None): 581 582 in_edges = self._region_in_edges(graph, region, data=True) 583 out_edges = self._region_out_edges(graph, region, data=True) 584 585 nodes_set = set() 586 for node_ in list(region.graph.nodes()): 587 nodes_set.add(node_) 588 if node_ is not dummy_endnode: 589 graph.remove_node(node_) 590 591 graph.add_node(region) 592 593 for src, _, data in in_edges: 594 if src not in nodes_set: 595 graph.add_edge(src, region, **data) 596 597 for _, dst, data in out_edges: 598 if dst not in nodes_set: 599 graph.add_edge(region, dst, **data) 600 601 if frontier: 602 for frontier_node in frontier: 603 if frontier_node is not dummy_endnode: 604 graph.add_edge(region, frontier_node) 605 606 if secondary_graph is not None: 607 self._abstract_acyclic_region(secondary_graph, region, { }) 608 609 @staticmethod 610 def _abstract_cyclic_region(graph, loop_nodes, head, normal_entries, abnormal_entries, normal_exit_node, 611 abnormal_exit_nodes): 612 region = GraphRegion(head, None, None, None, True) 613 614 subgraph = networkx.DiGraph() 615 region_outedges = [ ] 616 617 graph.add_node(region) 618 for node in loop_nodes: 619 subgraph.add_node(node) 620 in_edges = list(graph.in_edges(node, data=True)) 621 out_edges = list(graph.out_edges(node, data=True)) 622 623 for src, dst, data in in_edges: 624 if src in normal_entries: 625 graph.add_edge(src, region, **data) 626 elif src in abnormal_entries: 627 data['region_dst_node'] = dst 628 graph.add_edge(src, region, **data) 629 elif src in loop_nodes: 630 subgraph.add_edge(src, dst, **data) 631 elif src is region: 632 subgraph.add_edge(head, dst, **data) 633 else: 634 assert 0 635 636 for src, dst, data in out_edges: 637 if dst in loop_nodes: 638 subgraph.add_edge(src, dst, **data) 639 elif dst is region: 640 subgraph.add_edge(src, head, **data) 641 elif dst is normal_exit_node: 642 region_outedges.append((node, dst)) 643 graph.add_edge(region, dst, **data) 644 elif dst in abnormal_exit_nodes: 645 region_outedges.append((node, dst)) 646 # data['region_src_node'] = src 647 graph.add_edge(region, dst, **data) 648 else: 649 assert 0 650 651 subgraph_with_exits = networkx.DiGraph(subgraph) 652 for src, dst in region_outedges: 653 subgraph_with_exits.add_edge(src, dst) 654 region.graph = subgraph 655 region.graph_with_successors = subgraph_with_exits 656 if normal_exit_node is not None: 657 region.successors = [normal_exit_node] 658 else: 659 region.successors = [ ] 660 region.successors += list(abnormal_exit_nodes) 661 662 for node in loop_nodes: 663 graph.remove_node(node) 664 665 return region 666 667 @staticmethod 668 def _region_in_edges(graph, region, data=False): 669 670 return list(graph.in_edges(region.head, data=data)) 671 672 @staticmethod 673 def _region_out_edges(graph, region, data=False): 674 675 out_edges = [ ] 676 for node in region.graph.nodes(): 677 out_ = graph.out_edges(node, data=data) 678 for _, dst, data_ in out_: 679 if dst in region.graph: 680 continue 681 out_edges.append((region, dst, data_)) 682 return out_edges 683 684 def _remove_node(self, graph, node): # pylint:disable=no-self-use 685 686 in_edges = [ (src, dst, data) for (src, dst, data) in graph.in_edges(node, data=True) if not src is node ] 687 out_edges = [ (src, dst, data) for (src, dst, data) in graph.out_edges(node, data=True) if not dst is node ] 688 689 if len(in_edges) <= 1 and len(out_edges) <= 1: 690 # it forms a region by itself :-) 691 new_node = None 692 693 else: 694 new_node = MultiNode([ node ]) 695 696 graph.remove_node(node) 697 698 if new_node is not None: 699 for src, _, data in in_edges: 700 graph.add_edge(src, new_node, **data) 701 702 for _, dst, data in out_edges: 703 graph.add_edge(new_node, dst, **data) 704 705 def _merge_nodes(self, graph, node_a, node_b, force_multinode=False): # pylint:disable=no-self-use 706 707 in_edges = list(graph.in_edges(node_a, data=True)) 708 out_edges = list(graph.out_edges(node_b, data=True)) 709 710 if not force_multinode and len(in_edges) <= 1 and len(out_edges) <= 1: 711 # it forms a region by itself :-) 712 new_node = None 713 714 else: 715 new_node = MultiNode([ node_a, node_b ]) 716 717 graph.remove_node(node_a) 718 graph.remove_node(node_b) 719 720 if new_node is not None: 721 graph.add_node(new_node) 722 723 for src, _, data in in_edges: 724 if src is node_b: 725 src = new_node 726 graph.add_edge(src, new_node, **data) 727 728 for _, dst, data in out_edges: 729 if dst is node_a: 730 dst = new_node 731 graph.add_edge(new_node, dst, **data) 732 733 assert not node_a in graph 734 assert not node_b in graph 735 736 def _absorb_node(self, graph, node_mommy, node_kiddie, force_multinode=False): # pylint:disable=no-self-use 737 738 in_edges_mommy = graph.in_edges(node_mommy, data=True) 739 out_edges_mommy = graph.out_edges(node_mommy, data=True) 740 out_edges_kiddie = graph.out_edges(node_kiddie, data=True) 741 742 if not force_multinode and len(in_edges_mommy) <= 1 and len(out_edges_kiddie) <= 1: 743 # it forms a region by itself :-) 744 new_node = None 745 746 else: 747 new_node = MultiNode([node_mommy, node_kiddie]) 748 749 graph.remove_node(node_mommy) 750 graph.remove_node(node_kiddie) 751 752 if new_node is not None: 753 graph.add_node(new_node) 754 755 for src, _, data in in_edges_mommy: 756 if src == node_kiddie: 757 src = new_node 758 graph.add_edge(src, new_node, **data) 759 760 for _, dst, data in out_edges_mommy: 761 if dst == node_kiddie: 762 continue 763 if dst == node_mommy: 764 dst = new_node 765 graph.add_edge(new_node, dst, **data) 766 767 for _, dst, data in out_edges_kiddie: 768 if dst == node_mommy: 769 dst = new_node 770 graph.add_edge(new_node, dst, **data) 771 772 assert not node_mommy in graph 773 assert not node_kiddie in graph 774 775 @staticmethod 776 def _dbg_block_list(blocks): 777 return [(hex(b.addr) if hasattr(b, 'addr') else repr(b)) for b in blocks] 778 779 780register_analysis(RegionIdentifier, 'RegionIdentifier') 781