Node Commoning in Function Call Graph

Problem Statement

Problem Description You are given a directed acyclic graph that represents an execution of function calls and their operands. The data structure for the graph nodes is provided via the Call class. Your goal is to implement the node_commoning(call) function that performs Node Commoning (Common Subexpression Elimination) . The function should find all common chains of Calls/Nodes and transform the graph so that identical sets of Calls/Nodes are extracted and occur just once in the output graph, rather than multiple times. Two nodes are considered equivalent and should be commoned if they have the same operation ( _op ) and exactly the same operands ( _operand ) in the exact same order. Initial Code Structure class Call: def __init__(self, op): self._op = op self._operand = [] def __call__(self, *n): self._operand.extend(list(n)) return self def print_graph(call, done=None): if done is None: done = {} if call not in done: args = [] for n in call._operand: args.append(print_graph(n, done))