Bounded Dynamic Level Maintenance for Efficient Logic Optimization

Logic optimization is a critical phase in Electronic Design Automation (EDA) flow for meeting desired circuit power, performance, and area (PPA) targets. These logic circuits are typically represented as Directed Acyclic Graphs (DAGs), where the structural depth, quantified by node level, critically correlates with timing performance. Modern optimization strategies frequently employ iterative, local transformation heuristics (e.g., rewrite, refactor) directly on this DAG structure. As optimization locally modifies the graph, node levels require dynamic updates to guide subsequent decisions. However, a significant gap exists: existing algorithms for incrementally updating node levels are unbounded to small changes. This leads to a worst total complexity in O(|V |2) for given local subgraphs {ΔGi}|V | i=1 updates on DAG G(V,E). This unbounded nature poses a severe efficiency bottleneck, hindering the scalability of optimization flows, particularly when applied to large circuit designs prevalent today. In this paper, we analyze the dynamic level maintenance problem endemic to iterative logic optimization, framing it through the lens of partial topological order. Building upon the analysis, we present the first bounded algorithm for maintaining level constraints, with O(|V |Δlog Δ) time for a sequence |V | of updates {ΔGi}, where Δ=maxi _ΔGi_ denotes the maximum extended size of ΔGi. Experiments on comprehensive benchmarks show our algorithm enables an average 6.4× overall speedup relative to rewrite and refactor, driven by the proposed bounded maintenance that achieves subquadratic time updates, all without any quality sacrifice.