IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
1
Graph-Based ECO and Patch Generation for High-Level Synthesis
arXiv:2604.14248v1 [cs.SE] 15 Apr 2026
Alireza Azadi, Paul Rigge, Ethan Mahintorabi, and Kenneth B. Kent
Abstract—High-level synthesis (HLS) tools offer limited support for Engineering Change Orders (ECOs), making latestage design modifications challenging and costly. This paper introduces a graph-based ECO methodology tailored for Google XLS. A Graph Edit Distance (GED) algorithm is used to detect structural differences between original and revised intermediate representations (IRs), which are then transformed into patch operations. A patch application mechanism is developed to enforce XLS IR constraints while preserving semantic correctness, together with a schedule constraining scheme that maintains the original pipeline registers. Experiments across several XLS designs demonstrate high structural reuse ratios, effective schedule preservation, and full functional correctness, highlighting the practicality of the approach for production HLS flows. Index Terms—Engineering Change Orders, High-Level Synthesis, Graph Edit Distance, Google XLS, ASIC Design, Electronic Design Automation
I. I NTRODUCTION
E
NGINEERING Change Orders (ECOs) play a critical role in enabling late-stage modifications to hardware designs, particularly in ASIC development, where the cost and time associated with late-stage changes are significant. While traditional ECO methods focus primarily on Register-Transfer Level (RTL) designs, they often fall short in the context of High-Level Synthesis (HLS), where small high-level changes can drastically alter output RTL due to heavy optimizations, compiler transformations, and scheduling variations inherent in HLS flows. Google XLS, the focus of this paper, is an open-source HLS toolchain featuring frontends that transform high-level code into optimized and scheduled IR. However, minor high-level modifications can produce unpredictable effects on the postoptimized IR due to cascading optimization and scheduling transformations. This unpredictability makes it difficult to trace change impacts, and since RTL is directly derived from the IR, the absence of HLS-level ECO capabilities limits effective change management throughout the design flow, ultimately constraining RTL-level ECO and compromising design flexibility at the chip level. To demonstrate the core concept of our approach, we present a minimal example in Figure 1. Starting from a simple arithmetic IR implementing ret = (a + b) * c, we modify it to ret = a - (b * c). This seemingly small change requires structural edits at the IR level, including deletion and insertion of nodes and edges. Our ECO flow identifies these Alireza Azadi and Kenneth B. Kent are with the Faculty of Computer Science, University of New Brunswick, Fredericton, NB, Canada (e-mail: [email protected]; [email protected]). Paul Rigge and Ethan Mahintorabi are with Google, Mountain View, CA, USA (e-mail: [email protected]; [email protected]). The source code and test cases are available at https://github.com/alirezazd/ xls-eco/tree/eco-paper-2025.
a
b
c
a
b
c
umul
add
ret:umul
ret:sub
(a) Original IR
(b) Patched IR
1. Delete edge 2. Delete edge 3. Delete edge 4. Delete node 5. Change node 6. Insert node 7. Change edge 8. Insert edge 9. Insert edge 10.Insert edge
(a, add, 0) (add, ret:umul, 0) (b, add, 1) add ret:umul → umul ret:sub (c, ret:umul, 1) → (c ,umul, 1) (a, ret:sub, 0) (b, umul, 0) (umul, ret:sub, 1)
(c) Patch Operations
Fig. 1: Illustration of IR patching: (a) original IR implementing ret = (a + b) * c; (b) patched IR implementing ret = a - (b * c); (c) patch operations generated by the diff tool. Newly inserted nodes and edges are highlighted with boldness and gray fill. Reused elements are preserved without change. differences, generates a compact patch, and applies it while reusing unchanged parts of the original IR. The patch listing summarizes the precise edit operations computed by the tool. This paper proposes a novel graph-based ECO flow specifically targeting XLS IR. The methodology utilizes Graph Edit Distance (GED) techniques to calculate minimal transformation paths between the original and modified IRs. These paths are translated into patch operations, ensuring that changes are applied while respecting the integrity of the original design. Key features of the proposed approach include a GED-based diffing tool that incorporates XLS-aware cost metrics, a patch application mechanism that maintains structural correctness, and a schedule-constraining scheme to preserve timing alignment. The approach is evaluated on several real-world XLS designs, demonstrating high structural reuse (up to 95%), effective schedule preservation (up to 92%), and correctness through functional equivalence verification. The contributions of this work are as follows: • A complete end-to-end ECO methodology tailored for XLS IR, offering a systematic solution to address the challenges of late-stage design modifications. • A GED-based graph differencing tool that incorporates structural semantics, ensuring precise and effective IR transformations. • A robust patch generation and application mechanism
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
that minimizes disruptions to the original design, ensuring structural and semantic correctness. • A schedule-preserving approach that retains cycle-level timing and ensures RTL timing alignment in the final design. • Extensive evaluation on diverse XLS designs, demonstrating high reuse ratios, minimal structural changes, and efficient runtime performance. Our complete ECO methodology is fully implemented in an open-source flow based on Google’s XLS framework [1]. The rest of the paper is organized as follows: Section II provides background on high-level synthesis, the XLS framework, and GED algorithms. Section III reviews related work in ECO methodologies at both the high-level and RTL levels. Section IV outlines the proposed ECO flow and its components. Section V presents the experimental setup, results, and performance analysis of the proposed methodology. Finally, Section VI concludes the paper and suggests directions for the future work. II. BACKGROUND This section provides essential background on the key technologies and concepts underlying the ECO methodology, including an overview of High-Level Synthesis and its role in modern hardware design, a description of Google XLS and its IR, and, finally, Graph Edit Distance as the theoretical foundation of the approach. A. High-Level Synthesis (HLS) As indicated by Moore’s Law [2] increasing transistor density inherently drives greater hardware design complexity. Initially, hardware designers relied on RTL languages like Verilog and VHDL, which provided a structured way to describe digital circuits but still required meticulous low-level design efforts. However, as designs grew more complex, the need for higher levels of abstraction became apparent. High-Level Synthesis (HLS) has been a major focus of CAD researchers since the late 1970s [3], aiming to bridge the gap between algorithmic descriptions and hardware implementation. By the 1990s, the first generation of commercial HLS tools became available [4], marking a shift toward automation in hardware design. HLS not only abstracts hardware description but also facilitates system-level exploration, enabling architectural decisions related to hardware-software partitioning, memory organization, and power management. Like the relationship between assembly language and high-level programming, RTL provides precise control over hardware optimizations, while HLS enables a more abstract design flow that accelerates development. Though not as optimized as handcrafted RTL, HLS automates tasks such as concurrency management, pipeline insertion and control logic synthesis [5]. B. Google XLS Google XLS (Accelerated HW Synthesis) [6] is an opensource hardware design toolchain used both internally at Google and by the wider research community [7]–[9]. XLS
2
provides a flexible intermediate representation (IR) tailored for dataflow computations. The general flow of XLS involves describing hardware at a high level in DSLX or C++, which is then converted to IR. The IR undergoes multiple optimization passes such as arithmetic simplification and conditional specializations before producing a post-optimized IR. The IR is then scheduled into a pipelined implementation, from which register-transfer level (RTL) code is generated C. Graph Edit Distance (GED) Algorithms Graph Edit Distance (GED) is a fundamental metric for quantifying the dissimilarity between two graphs. It is defined as the minimum-cost sequence of operations, namely, node and edge insertions, deletions, or substitution required to transform one graph into another. Formally, given two graphs G1 and G2 , the GED is defined as: X GED(G1 , G2 ) = min cost(o) (1) P ∈P(G1 ,G2 )
o∈P
where P(G1 , G2 ) is the set of all valid edit paths transforming G1 into G2 , and cost(o) denotes the cost of an individual edit operation o. While GED yields a scalar distance, Graph Edit Paths (GEPs) extend this notion by explicitly returning the sequence of edit operations, enabling interpretability in transformation scenarios. GED is widely adopted in domains such as pattern recognition, bioinformatics, and circuit optimization, where both similarity assessment and precise structural modifications are essential. Abu-Aisheh et al. [10] propose DF-GED, an exact GED algorithm based on depth-first branch-andbound search. The algorithm leverages precomputed vertex and edge cost matrices as well as a Munkres-based sorting [11] of source nodes to prioritize promising mappings early. While the worst-case time complexity remains exponential, DF-GED demonstrates significant empirical gains in both runtime and memory efficiency. The DF-GED algorithm is implemented as part of the NetworkX library [12] and we found it to be a good candidate to demonstrate our methodology in this paper due to the flexibility of NetworkX which allows us to represent our IR as a graph and the exact output that is mandatory for the functional correctness of ECO. III. R ELATED W ORK Although ECO methodologies have been extensively studied at the RTL and gate levels, only a limited academic efforts study this important challenge for High-Level Synthesis (HLS) [13], [14]. ECO at the HLS level poses unique difficulties due to the higher level of abstraction, where even minor source changes can trigger widespread and unpredictable transformations in the resulting netlist [13]. This complicates change localization and makes the design of scalable patching mechanisms more difficult. In this section, we review prior ECO methodologies from HLS to gate level, focusing on patch generation, scheduling preservation, and the availability of supporting tools. A comparative summary is provided in Table I, which includes our proposed graph-based ECO flow. This comparison underscores the key characteristics of our approach, including fine-grained
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
3
TABLE I: Comparison of ECO methodologies against our graph-based HLS flow Work
Target Level
Technique
Patch Granularity
Schedule Preservation
Open Source
This Work Alizadeh et al. [14] Lavagno et al. [13] Wang et al. [15]
HLS HLS HLS HLS
Individual Nodes & Edges Connections & Muxes Operator-Level Operator-Level
Yes Yes Partial No
Yes No No No
Alizadeh et al. [16] Zhang et al. [17] Dao et al. [18] Cheng et al. [19]
RTL Gate Gate Gate
Region-level Logic Cone Logic Cone Logic Cone
No N/A N/A N/A
No No No No
Kravets et al. [20] Krishnaswamy et al. [21]
Gate Gate
GED SMT String Diff Programmable Datapath + SMT/QBF Subgraph Match QBF-guided Rectification SAT-based Patch Synthesis Craig Interpolation + Greedy Heuristics SAT + Symbolic Sampling Structural Hashing + SAT
Logic Cone Logic Cone
N/A N/A
No No
patching at the graph level, robust schedule preservation and full integration within an open-source flow, while also identifying areas where prior work leaves room for improvement.
A. High-Level ECO Methods Post-synthesis ECO methods operate on gate-level netlists. At the gate level, operation-level scheduling and pipeline timing constraints are no longer explicitly available and are resolved earlier, during high-level or RTL synthesis. As a result, post-HLS ECO techniques focus on functional correctness and structural patching, rather than preserving operation schedules. Alizadeh et al. [14] propose a datapath-aware ECO synthesis method targeting the high-level synthesis stage. Their approach aims to preserve the original datapath structure by reusing existing functional units and registers. To achieve this goal, they selectively modify the scheduling and binding phases and utilize an SMT-based formulation to minimize changes to connections and multiplexers. It is worth noting that their methodology is implemented within a custom toolchain, and its compatibility with commercial or open-source HLS flows has not been demonstrated. Lavagno et al. [13] propose an incremental high-level synthesis approach to enable ECO support by reusing scheduling and binding decisions across synthesis runs. Their methodology operates on SystemC inputs and internal Control-Data Flow Graph (CDFG) representations. Similar to our approach, they utilize diffing techniques for change detection; however, their method relies on string-based differencing of linearized graphs, whereas our approach employs graph-based differencing. Their patching is at the operation level (nodes), and their scheduling preservation is partial: prior decisions are reused if valid, but otherwise discarded. Their approach, implemented within a proprietary synthesis framework, lacks robustness when small source changes introduce new constraints. If prior scheduling decisions become invalid, the tool discards them entirely instead of selectively preserving what remains feasible. Wang et al. [15] propose a methodology for ECO centered around use of programmable datapaths, by formulating equivalence and leveraging SMT solving using Z3 [22] to derive valid datapath configurations. Patch generation is performed by rerouting through spare operators using multiplexer control
signals, making their patch scope operator-level. This method demonstrates potential for small-scale designs, however, their approach struggles with larger datapaths due to solver complexity. In terms of reproducibility, their work is based on a custom flow that is not integrated into any open-source or commercial HLS framework. Unlike our ECO methodology, which integrates a schedule-constraining phase to preserve RTL timing alignment, Wang et al.’s method does not address scheduling or pipeline preservation. Their focus remains at the datapath control level, assuming structural reuse will inherently maintain timing; a limitation in sequential or deeply pipelined designs. B. Post-HLS ECO In a subsequent study [16], Alizadeh et al. shift their focus to the RTL level, proposing a method that synthesizes localized patches by extracting subgraphs from the RTL and a C/C++ reference. Their patch granularity is region-level, targeting entire datapath structures. Their methodology emphasizes datapath preservation and as a result, it may overlook updates to combinational logic, such as those introduced by pipelining optimizations. Zhang et al.’s work on cost-aware RTL ECO patch generation [17] uses Quantified Boolean Formula (QBF) reasoning to find minimal sets of input signals (support) needed to generate gate-level patches that are functionally correct and efficient in area. The generated patches target logic cones, meaning that each patch replaces or rewires the entire logic required to compute a target signal, rather than modifying fine-grained gates. While the proposed technique effectively targets structurally conservative ECOs, it operates within a closed academic toolchain with limited reproducibility. Dao et al. [18] propose a SAT-based ECO methodology targeting post-synthesis gate-level netlists. Their flow synthesizes logic patch functions using cube enumeration and QBF enhancements. Like Zhang et al.’s approach, their patches operate at the logic cone level. While functionally robust, their approach assumes that structural reuse is sufficient for timing preservation and does not address scheduling or pipeline alignment. Dao et al.’s work is reproducible to some extent for experts familiar with ABC and SAT-based flows, but the absence of released scripts and tool modifications imposes significant engineering effort to replicate. Cheng et al. [19]
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
present a resource-aware ECO methodology that improves patch feasibility by selecting support signals based on physical and structural accessibility within the gate-level netlist. Their approach integrates Craig interpolation with greedy support selection heuristics. Like other gate-level approaches, their patches operate at the logic cone level. Kravets et al. [20] present a robust ECO rectification methodology for gate-level designs, where structural dissimilarity between the optimized implementation and the revised specification complicates patch generation. Their approach uses symbolic sampling and SATbased reasoning to identify rectification points and synthesize minimal-impact rewiring patches. While highly effective for post-synthesis, their methodology is not integrated with opensource toolchains, which limits reproducibility. Krishnaswamy et al.’s work on DeltaSyn [21] targets gate-level ECO by identifying and optimizing logic differences between the original synthesized netlist and a new netlist derived from revised RTL. DeltaSyn is presented as a research prototype and combines Boolean subcircuit matching, structural hashing, and SAT-based validation to detect changed logic cones and generate minimal-area patches. While DeltaSyn is not directly reproducible due to the absence of source code and tooling details, the conceptual flow reasonably well-described and can be replicated by experts in the field.
C. Commercial Tools Several commercial HLS tools have introduced incremental and ECO-aware capabilities, although their scope and transparency vary significantly. Cadence Stratus HLS offers the most direct support for HLS-level ECO flows, featuring a dedicated ECO mode that prioritizes RTL similarity over reoptimization when minor high-level changes occur. This mode is tightly integrated with Cadence’s Conformal ECO and logic synthesis tools with support for bidirectional mapping between RTL and the source code [23], [24]. Siemens Catapult HLS supports incremental compilation through caching scheduling and binding results across runs. When applied correctly, this preserves the micro-architecture of unchanged modules, leading to stable RTL and behavior under minor C++/SystemC edits [25]. Xilinx Vitis HLS and Intel HLS Compiler enable ECO-like flows primarily through downstream reuse via hierarchical partitioning and incremental compilation. [26], [27]. IV. M ETHODOLOGY The flowchart in Figure 2 illustrates the systematic process of applying and validating an ECO to an IR in XLS. The process begins with the comparison of the “Original IR” and “Revised IR” through the “Diff” tool, which subsequently generates a “Patch.” This patch is then applied to the original IR, producing a “Patched IR.” The flow then proceeds to constrain the schedule, ensuring that the original timing constraints are preserved. The final phase involves integrating the constrained schedule, design constraints, and the patched IR into the “Codegen” process, which produces the “Patched RTL.”
Original Schedule
4
Revised IR
Original IR
Design Constraints
Diff
Patch
Constrain Schedule
Apply Patch
Patched IR
Constrained Schedule
Scheduling Codegen
END
Patched RTL
Fig. 2: Overview of the XLS ECO Flow. Components with bold borders represent the proposed modules that are integrated into the original XLS flow. A. IR to NetworkX Parsing The initial step in the ECO flow is translating the XLS IR into a NetworkX MultiDiGraph representation. We developed an IR parser that converts XLS IR structures into graph representations suitable for graph-based analysis. The MultiDiGraph is well-suited for representing XLS IRs because: • It allows multiple parallel edges between the same nodes, which is essential for representing instances where multiple signals may connect the same pair of nodes. For example, a select node with multiple inputs producing the same constant value. This requires multiple edges from the constant literal node to the select node. • It inherently models the one-way flow of data between nodes, reflecting the static single-assignment (SSA) property and the lack of sequential control flow in XLS IRs. Additionally, our IR parser extracts the attributes of the nodes and edges in the graph. These attributes are later utilized by the diff tool. B. IR Diff Tool The IR diffing tool is a core component of the ECO flow, responsible for comparing two IRs and generating a set of edit operations to transform one graph into the other. As discussed in the background section, the diff tool operates based on cost functions for every node and edge operation. To accurately reflect the nuances of XLS IRs, we implemented custom cost functions based on a collection of the attributes of nodes and edges that were precomputed during the parsing stage. These functions are intended to guide the algorithm toward minimal edit paths while ensuring that the resulting transformations are feasible and valid within the XLS IR framework, as XLS IR enforces multiple structural rules that must be respected. The handling of these constraints is described in more detail in the Patching section. Table II lists the cost attributes used in the diffing process, grouped into node and edge categories: • Edge Cost Attributes: Although XLS IR does not explicitly represent edges, it models connectivity through
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
5
TABLE II: Node and Edge Cost Attributes Type
Attribute
Description
source_data_type
Data type of the source node
sink_data_type
Data type of the sink node
index
Position index for noncommutative edges
op
Operation type of the node
dtype_str
Data type of the node
operand_dtype_str
Data type of the operand node
Edge
Node
Unique Attribute(s)
Edge
Node
EditPath operation: INSERT/UPDATE/DELETE
NodeEditPath
EdgeEditPath
node: NodeInfo updated_node: NodeInfo[optional]
edge: EdgeInfo updated_edge: EdgeInfo[optional]
NodeInfo name op data_type operand_data_type(s) unique_attribs(s)
Specific to node type
TABLE III: Cost Assignment for Graph Edit Paths Type
IrPatch edit_paths: EditPath function_name return_node
Operation Substitution (identical attributes) Substitution (different attributes) Insertion Deletion Substitution (identical attributes) Substitution (different attributes) Insertion Deletion
Cost 0 ∞ 1 1 0 ∞ 1 1
node operands and users. When comparing IR edges structurally, data type compatibility between source and sink nodes is crucial. For instance, 4-bit to 8-bit connections cannot be substituted with 8-bit to 16-bit ones. The source_data_type and sink_data_type attributes ensure this compatibility during edge matching. For non-commutative operations, the index attribute preserves operation order since the sink position relative to other inputs must be explicitly tracked for noncommutative operations like concatenation. Only the sink index needs to be captured, while the source index position is not essential for maintaining structural semantics during graph comparison. • Node Cost Attributes: Nodes also include a standard set of attributes, with additional attributes for specific node types; many nodes, such as literals, have unique attributes, such as a value field, which are added to their respective unique attributes. These attributes allow the diff tool to effectively capture both common and unique characteristics of nodes, ensuring precise graph comparisons. Table III summarizes the costs applied during the diff process. The substitution cost function assigns an infinite cost to mismatched substitutions ensuring that the algorithm only opts for substitutions when cost attributes align. In other words, when a node or edge does not match its counterpart, the tool will find it more cost-effective to delete and then re-insert the node or the edge with the expected attributes, rather than a forced substitution with infinite cost. Meanwhile, insertions and deletions are given a uniform cost of 1, providing a consistent baseline for modifications and resulting in a simplified decision-making landscape.
EdgeInfo from_node to_node index
Fig. 3: Hierarchical structure of the patch protobuf.
C. Patching The patching process enables the systematic transformation of one IR into another by applying a series of well-defined node and edge insertions, deletions and substitutions. This process begins by iterating through the outputs of the IR diff, identifying differences, and capturing them in a structured format along with the necessary metadata. These differences are then exported to a protobuf to be consumed by the patch applier later in the flow. As shown in Figure 3, the protobuf structure is organized around the IrPatch class, which includes a series of EditPath operations. Each EditPath operation can pertain to either a node (NodeEditPath) or an edge (EdgeEditPath) edit operation. The NodeEditPath and EdgeEditPath further encapsulate metadata related to nodes (NodeInfo) and edges (EdgeInfo), respectively. 1) Patch Applier: The patch applier modifies the Intermediate Representation (IR) based on a sequence of edit instructions, ensuring minimal disruption to the existing IR structure while maintaining functional correctness. The IR enforces strict invariants that must be preserved throughout the modification process: • Invariant 1: A node’s operands are always populated with valid nodes. • Invariant 2: A node can only be deleted if it has no users. To handle these constraints, the patch applier adopts a staged approach that prioritizes operations, uses dummy nodes as temporary stand-ins and leverages dictionaries to track updates, ensuring structural integrity of the IR during the patching process. Patch Application Order: The patch application follows a specific order: 1) Edge deletions are performed first to disconnect nodes that will later be removed. This ensures safe removal of nodes and allows for edge updates or replacements without conflict. By prioritizing edge deletions, we avoid scenarios where an edge update would subsequently target a deleted edge. 2) After edge deletions, nodes can be safely removed since they no longer have incoming or outgoing edges, which
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
6
ensures that the IR remains consistent. During deletion, dummy nodes are used to maintain valid references for dependents, satisfying the first invariant. 3) Updates and insertions of nodes are prioritized over edge modifications to ensure that all dependencies for edge updates or insertions are already in place. This guarantees that new or updated edges have valid endpoints and dependencies. 4) Edge modifications are performed last. This guarantees that all nodes are already in their final state, allowing new or updated edges to connect valid endpoints without encountering missing dependencies. Dummy Nodes: These nodes are used for two primary purposes: 1) Before a node is deleted, it is replaced with a dummy node to maintain valid references for its dependents. This ensures that the IR remains structurally sound until the deletion is finalized. 2) New nodes are initially created with dummy operands that match the required data types. These temporary stand-ins allow the node to exist in a valid state until its final connections are established. During the patch application, we track which nodes have dummy nodes attached to them to facilitate proper cleanup. Dummy nodes are not removed or inserted independently; their lifecycle is tied to the patch operations. When an insertion operation replaces a dummy node with a real node or when the node they are attached to is deleted, the dummy nodes are removed automatically. By the time the patch is fully applied, The IR is expected to contain no dummy nodes; otherwise, their presence would suggest an error in the process. Replacing Updates with Dictionaries: Updates are handled without modifying existing nodes in the IR. When an update requires substituting a node (e.g., substituting foo to bar), the patch applier does not alter original node. Instead, it maintains a dictionary that maps the new node to the original node. From then on, any reference to foo is redirected to bar. For changes to the operand index of commutative operations (where operand order does not affect the operation’s result), the patch applier tracks index changes using a similar mechanism, which avoids unnecessary rewiring of nodes and edges. This approach aligns with the primary goal of the ECO which is minimizing disruption to the existing IR structure while maximizing reuse.
begins by examining each node in the original schedule’s cycle map. For each node, we first perform several qualification checks to determine if the node should be constrained: 1) Newly inserted nodes do not have an original placement to preserve, making them exempt. 2) Nodes that no longer exist in the modified IR cannot be constrained since they have been removed. 3) Literals are inherently flexible in their timing, and constraints are not applied to them. For every eligible node, we greedily apply cycle-level constraints, attempting to place the node in its original pipeline stage. The feasibility of this constraint is immediately verified by attempting to generate a complete pipeline schedule. The effectiveness of the constraining process can be measured by comparing the number of successfully constrained nodes against the total node count in the design.
D. Schedule Constraining:
B. Design Summary and ECO Types
The scheduling information in XLS directly determines the RTL structure produced by the codegen module. Since register names are derived from IR node names and their cycle assignments, the schedule becomes a crucial bridge between the IR representation and the final RTL implementation. When applying ECO, preserving the original schedule becomes essential for maintaining similarity between the original and revised RTLs. The schedule constraining phase attempts to maintain the cycle-level scheduling of common nodes in both versions of the design, while ensuring the resulting schedule remains feasible under the design’s timing constraints. The process
To comprehensively evaluate the ECO flow across a range of design complexities, we selected seven XLS designs spanning from small modules (e.g., CRC32) to large, dataflow-intensive pipelines (e.g., Vector Core). The node counts range from fewer than 100 to nearly 1000 nodes, offering a practical upper bound for assessing runtime and memory scalability within current infrastructure limits, as summarized in Table IV. Most of these designs are either directly taken from or adapted from the official examples in the open-source XLS repository. To fill complexity coverage gaps, two additional designs(Histogram, Vector Core) were developed specifically for this evaluation.
V. R ESULTS AND E VALUATION This section presents the evaluation results of the proposed ECO flow applied to a set of XLS designs, aiming to assess its effectiveness across different design scales and stages of the ECO flow. Our analysis highlights the structural reuse achieved through patch generation, the runtime performance of the graph differencing algorithm, and the effectiveness of schedule preservation during the ECO flow. All evaluated designs, ECO scripts, and generated patches can be reproduced from our open-source GitHub repository [1]. A. Experimental Setup All experiments were conducted on a Linux-based system (specifications: AMD EPYC 7B13, 64 cores, 128GB RAM, Debian Linux), and functional equivalence was verified using Cadence Conformal LEC v22.20. Large designs in our benchmark set, such as Vector Core and Histogram, caused Python recursion limit issues when running NetworkX GED. To address this, we manually increased the recursion threshold. This issue, combined with long runtimes for large designs, indicate that the current NetworkX implementation is nearing its scalability boundary and may benefit from future optimizations. As discussed in the Background section, our approach applies the GED algorithm iteratively. To maintain practical runtimes, we enforced a maximum time limit of 24 hours per design.
ECO Change Type
CRC32 ApFloat MAC Simple RISCV ZSTD Frame Decoder
Polynomial modification Increased exponent bit width Register read optimization Increased number of pipeline stages Refined multiplication by zero handling Fixed division by zero in last bin calculation Addressed integer overflow
FIR Filter Histogram Vector Core
Schedule Affected No No No
Yes Yes
These custom cases help ensure a more consistent progression across the design scales. The proposed ECO methodology was demonstrated through targeted modifications to seven distinct XLS designs, encompassing a range of changes from minor functional tweaks to significant structural rewrites. Table V summarizes the ECO changes introduced in each design and whether they affected the schedule. Notably, in the case of ZSTD Frame Decoder, the modification only altered the schedule by increasing the number of pipeline stages without changing the DSLX source. As a result, patch generation for this design is skipped and the flow proceeds directly to schedule constraining. C. Patch Generation and Application As outlined in the implementation section, the substitution operations are not directly applied, instead they are interpreted as preserving structural intent and therefore considered reused. In our analysis, we classify all non-deleted nodes and edges, including those involved in substitutions as reused, since they maintain connectivity and their functional role within the dataflow. Conversely, changes are defined as the sum of insertions and deletions, which represent structural modifications. We define the following quantities for each design. The reuse metric captures preserved structural elements: (2)
where Norig and Eorig are the original node and edge counts, and Ndel and Edel are the deleted counts. The change metric quantifies structural modifications: (3)
where Nadd and Eadd represent added nodes and edges. From these, we derive the reuse ratio: Reuse Ratio =
Reuse Reuse + Change
8%
5%
26%
34%
14%
0.6 0.2 0.0
2
at
Flo
Ap
-V
ISC
R ple
Sim
IR
le F
p Sim
m
gra
to His
91%
0.4
tor Vec
re
Co
Fig. 4: Fraction of reuse (substitutions and unchanged structure) versus structural modification (insertions and deletions) across all evaluated designs. Bars are normalized to total edit operations.
Design
Yes
Change = Nadd + Ndel + Eadd + Edel
Reuse Change
TABLE VI: Breakdown of node and edge edit operations for each design
Yes
Reuse = (Norig − Ndel ) + (Eorig − Edel )
0.8
C3 CR
TABLE V: Summary of Introduced Changes and Their Impact on Scheduling Design
1.0
95%
Scale Small Medium Medium Medium Medium Large Large
74%
Depth 35 28 41 11 79 56 56
66%
# Edges 74 305 420 825 1037 1460 2022
57%
# Nodes 54 177 260 418 593 807 988
86%
Design CRC32 ZSTD Frame Decoder ApFloat MAC Simple RISCV FIR Filter Histogram Vector Core
Fraction of Operations
TABLE IV: Experimental ECO Designs Characteristics
7
42%
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
(4)
CRC32 ApFloat Simple RISC-V FIR Histogram Vector Core
Add 1 57 11 47 3 11
Node Ops Del Sub 1 0 56 103 127 245 21 420 0 757 3 845
Add 8 162 161 373 96 253
Edge Ops Del Sub 8 0 162 142 391 405 337 571 91 1334 243 1662
Cost 18 437 690 778 190 510
and the complementary change ratio: Change Ratio = 1 − Reuse Ratio
(5)
Using equations (4) and (5), Figure 4 visualizes these ratios across all designs using a normalized stacked bar chart, while Table VI lists the corresponding raw operation counts. The results demonstrate mixed outcomes across different designs. This variability highlights a critical insight: the effects of small high-level source modifications on the post-optimized IR structure are difficult to predict reliably. Table VI shows the final generated patches; however, two designs (FIR and Histogram) produced multiple patches during execution. For FIR, intermediate patches with costs of 784 and 780 were generated before reaching the final patch cost of 778. Similarly, Histogram produced intermediate patches with costs of 202 and 196 before achieving the final cost of 190. The results show that substitution operations outnumber additions and deletions in most designs, particularly in larger ones. This confirms that our cost function implementation effectively captures the structural properties of the XLS IR. It is important to note that our reuse analysis is based on node count rather than hardware area. Different XLS node types have vastly different hardware costs; for example, multipliers may represent 80% of the design area while constituting only 5% of the total nodes. Therefore, a low node reuse ratio does not necessarily indicate poor area efficiency, as the preserved nodes might include the most area-intensive components. Figure 5 summarizes the computational requirements of the diff process, capturing both peak memory usage and total patch generation time across designs. As expected, RAM consumption increased with design complexity. Analysis of peak RAM usage in Figure 5(a) indicates non-linear memory growth as design complexity increases. While small designs (CRC32, ApFloat MAC) required less than 1GB of RAM,
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
25.1 GB
10.0 5.0
0.5 GB
6.8 GB
Design ZSTD Frame Decoder FIR Filter Histogram Vector Core
0.9 GB
C m IR -V re t MA le RISC mple F istogra r Co a o t o l c i p H S Ve ApF Sim
32
CRC
(a)
Patch Time (s)
104
14667s 365s
103 102
32s 101s
14s
101
188s
363s
32
CRC
AC
Ap
tM Floa
S
imp
IS le R
* * re FIR ogram ctor Co e l p t Ve Sim His
C-V
(b)
Fig. 5: Resource usage during ECO patch generation across designs: (a) Peak RAM consumption (log scale); (b) Total patch generation time (log scale); Designs marked with * yielded more than one patch during the algorithm’s execution, with the first patch time shown on their bar.
larger ones (Histogram, Vector Core) exhibited significant increases, reaching tens of gigabytes. Similar to the memory usage, the patch generation time, which is shown in Figure 5(b), also demonstrated a non-linear trend, with smaller designs completing in under a minute, while larger designs (Histogram, Vector Core) taking over an hour to generate patches.
Skipped Nodes Infeasible Newly Inserted 1 0 55 0 93 0 46 2
80.0%
80
40 20 0
er
ead
FIR
r Filte
gra
o Hist (a)
m
tor Vec
e Cor
345s
300
177s
200
174s
100 0
D ZST
92.0%
78.0%
60
H ame
ZST
Literal 25 22 27 13
87.0%
D Fr
<1s
100
TABLE VII: Schedule Constraining Summary for Selected Designs
Preservation Ratio (%)
1.0 0.5
2.7 GB
51.4 GB
Constraining Time (s)
Peak RAM (GB)
50.0
8
ea eH
17s
der
Fram
ilter IF R F
ram
og Hist
ore
C tor Vec
(b)
Fig. 6: Schedule preservation across designs: (a) Percentage of nodes with preserved schedule constraints; (b) Total time taken to resolve schedule constraints. explore more sophisticated schedule constraining approaches.
D. Schedule Preservation The results presented in Table VII and Figure 6 highlight the relationship between the number of structurally infeasible nodes and both the achieved preservation ratio and the runtime required for constraint resolution. Designs with fewer infeasible scheduling constraints, such as ZSTD Frame Decoder, yielded high preservation ratios (87%) and short runtimes (17 seconds). In contrast, designs exhibiting a higher count of infeasible nodes, such as Histogram, resulted in lower preservation (78%) and significantly increased runtimes (345 seconds). The presence of literal-skipped nodes, which ranged similarly across designs (20–27 nodes), had minimal impact on both preservation and runtime. The results demonstrate that the proposed scheduling preservation scheme is effective across a range of design complexities, with over 75–90% of original schedule constraints successfully preserved across all evaluated designs. Given this practical effectiveness, we did not
E. Verification To evaluate the correctness of the proposed ECO flow, we performed equivalence checking at both the IR and RTL levels using XLS’s built-in Z3-based verifier [28] and Cadence Conformal LEC. Among the seven benchmark designs, five were function-based, and two (Histogram and ApFloat MAC) were proc-based. Table VIII summarizes the verification outcomes; for function-based designs, IR-level equivalence was successfully established. Specifically, the equivalence was verified between the revised IR, generated from the modified design, and the patched IR, which was derived from the original design by reusing unchanged components. This confirms that the patching process preserved the intended functionality. However, since XLS’s Z3-based equivalence checker only supports function-based designs, IR-level verification could not
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
TABLE VIII: Summary of Verification Results Design CRC32 ZSTD Decoder ApFloat MAC Simple RISC-V FIR Filter Histogram Vector Core
Type Function Function Proc Function Function Proc Function
RTL Equiv. Passed Passed Passed Passed State mismatch Not completed State mismatch
IR Equiv. Passed Passed N/A Passed Passed N/A Passed
be applied to Histogram and ApFloat MAC, which are procbased and involve explicit state and scheduling constructs. To address this, we used Cadence Conformal LEC for RTL-level verification of the proc-based designs. While ApFloat MAC passed RTL-level equivalence checking, Histogram could not complete verification within a reasonable time due to the design’s large number of registers and pipeline state elements. In summary, while some verification limitations remain, especially for designs with complex RTL states, we validated most benchmarks using the available tools, and the results confirm the functional correctness of our ECO flow. Future work should explore more robust verification strategies for handling structural differences in stateful RTL designs. VI. C ONCLUSION AND FUTURE WORK Our evaluation reveals that the proposed approach scales across design complexities, from small modules to nontrivial dataflow-heavy pipelines, while maintaining high reuse ratios. The patch applier module, guided by customized cost functions, enables transformations that respect the structural constraints of XLS. Applying graph edit sequences in this context requires systematic updates while preserving functional behavior. Furthermore, the schedule constraint scheme effectively preserves original timing annotations, helping to align more internal states in sequential designs and thereby facilitating equivalence checking in downstream tools and reducing the complexity of later netlist-level ECOs. Our complete flow, including parser, diff tool, patch applier, and test designs, is available as an open-source project for the research community [1]. As for future work, we aim to address several key areas for improvement: (1) Improving scalability for large designs, the current implementation uses a single-threaded GED algorithm, which limits performance on complex graphs. The authors of the core GED algorithm used in our work have also introduced a multi-threaded variant [29], which presents a promising direction for future work. Adapting this parallelized approach to XLS IRs could substantially enhance runtime performance. Additionally, machine learning-based approaches could accelerate and scale up the process of graph matching, either as standalone solutions [30]–[32] or as hybrid approaches that combine classical algorithms with ML techniques [33]. (2) Enhancing verification support, as mentioned in the verification section, in scenarios where schedules differ, despite IRlevel functional equivalence, conventional sequential equivalence checking may fail due to mismatched states. In these cases, tools like Synopsys Formality or hybrid RTL-vs-IR equivalence techniques may offer more robust validation. (3)
9
Increasing automation, several stages of our flow, such as feeding diff outputs into the patch applier or identifying schedule divergences through register comparison, currently require manual effort. Developing automated pipelines for such tasks would enhance usability and streamline the ECO process, making it more accessible to users unfamiliar with the underlying XLS IR structure. R EFERENCES [1] A. Azadi, “Xls eco results repository,” https://github.com/alirezazd/ xls-eco/tree/eco-paper-2025, 2025, accessed: 2025-09-08. [2] G. Moore, “Cramming more components onto integrated circuits,” Proceedings of the IEEE, vol. 86, no. 1, pp. 82–85, 1998. [3] G. Martin and G. Smith, “High-level synthesis: Past, present, and future,” IEEE Design & Test of Computers, vol. 26, no. 4, pp. 18–25, 2009. [4] P. Coussy, D. D. Gajski, M. Meredith, and A. Takach, “An introduction to high-level synthesis,” IEEE Design & Test of Computers, vol. 26, no. 4, pp. 8–17, 2009. [5] R. Kastner, J. Matai, and S. Neuendorffer, “Parallel Programming for FPGAs,” ArXiv e-prints, May 2018. [6] Google, “Google xls: High-level synthesis framework,” 2024, accessed: 2025-09-08. [Online]. Available: https://google.github.io/xls [7] J. Ma, C. Xu, and L. W. Wills, “Pytfhe: An end-to-end compilation and execution framework for fully homomorphic encryption applications,” in 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 2023, pp. 24–34. [8] Antmicro, “Accelerating digital block design with google’s xls,” 2023, accessed: 2025-09-08. [Online]. Available: https://antmicro.com/blog/ 2023/09/accelerating-digital-block-design-with-googles-xls/ [9] H. Ye, D. Z. Pan, C. Leary, D. Chen, and X. Xu, “Subgraph extractionbased feedback-guided iterative scheduling for hls,” in 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE), 2024, pp. 1–6. [10] Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, and P. Martineau, “An exact graph edit distance algorithm for solving pattern recognition problems,” in Proceedings of the 4th International Conference on Pattern Recognition Applications and Methods, Lisbon, Portugal, January 2015. [11] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/nav. 3800020109 [12] NetworkX Developers, NetworkX: optimize edit paths, NetworkX Project, 2025, online; accessed 8 September 2025. [Online]. Available: https://networkx.org/documentation/latest/reference/algorithms/ generated/networkx.algorithms.similarity.optimize edit paths.html [13] L. Lavagno, A. Kondratyev, Y. Watanabe, Q. Zhu, M. Fujii, M. Tatesawa, and N. Nakayama, “Incremental high-level synthesis,” in 2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC), 2010, pp. 701–706. [14] M. Shiroei, B. Alizadeh, and M. Fujita, “Data-path aware high-level eco synthesis,” Integration, vol. 65, pp. 88–96, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167926018303766 [15] R.-Y. Wang, C.-C. Pai, J.-J. Wang, H.-T. Wen, Y.-C. Pai, Y.-W. Chang, J. C.-M. Li, and J.-H. R. Jiang, “High-level eco via programmable datapath and smt,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), 2019, pp. 1–5. [16] B. Alizadeh and M. Shiroei, “Automatic correction of rtl designs using a lightweight partial high level synthesis,” Integration, vol. 91, pp. 173–181, 2023. [Online]. Available: https://www.sciencedirect.com/ science/article/pii/S0167926023000573 [17] H.-T. Zhang and J.-H. R. Jiang, “Cost-aware patch generation for multitarget function rectification of engineering change orders,” in 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC), 2018, pp. 1–6. [18] A. Q. Dao, N.-Z. Lee, L.-C. Chen, M. P.-H. Lin, J.-H. R. Jiang, A. Mishchenko, and R. Brayton, “Efficient computation of eco patch functions,” in Proceedings of the 55th Annual Design Automation Conference, ser. DAC ’18. New York, NY, USA: Association for Computing Machinery, 2018. [Online]. Available: https://doi.org/10.1145/3195970.3196039 [19] A.-C. Cheng, H.-R. Jiang, and J.-Y. Jou, “Resource-aware functional eco patch generation,” in Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE), 2016, pp. 1037–1042.
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
[20] V. N. Kravets, N.-Z. Lee, and J.-H. R. Jiang, “Comprehensive search for eco rectification using symbolic sampling,” in Proceedings of the 56th Annual Design Automation Conference (DAC), 2019, pp. 71:1–71:6. [21] S. Krishnaswamy, H. Ren, N. Modi, and R. Puri, “Deltasyn: An efficient logic difference optimizer for eco synthesis,” in 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, 2009, pp. 789–796. [22] L. de Moura and N. Bjørner, “Z3: An efficient SMT solver,” in Tools and Algorithms for the Construction and Analysis of Systems (TACAS), ser. Lecture Notes in Computer Science, vol. 4963. Springer, 2008, pp. 337–340. [23] D. Pursley, “Eco with stratus hls and the digital implementation flow,” Cadence Community Blog, 2018, accessed: 2025-09-08. [Online]. Available: https://community.cadence.com/cadence blogs 8/b/di/posts/ eco-with-stratus-hls [24] Cadence Design Systems, “Cadence announces stratus high-level synthesis platform,” https://www.prnewswire.com/news-releases/ cadence-announces-stratus-high-level-synthesis-platform-300038873. html, 2015, press release, accessed 2025-09-08. [25] M. Dunn, “Catapult 8 a major hls upgrade,” EDN Network, 2014, accessed: 2025-09-08. [Online]. Available: https://www.edn.com/ catapult-8-a-major-hls-upgrade/ [26] Intel Corporation, “Rapid recompile,” https://www.intel.com/content/ www/us/en/software/programmable/quartus-prime/rapid-recompile. html, 2023, accessed: 2025-09-08. [27] AMD Xilinx, “Enable faster design iterations with incremental compile and abstract shell in vivado,” https://www.amd.com/en/products/ software/adaptive-socs-and-fpgas/vivado/faster-design-iterations.html, 2023, accessed: 2025-09-08. [28] Google, “Xls: Z3-based ir equivalence checker,” https://github.com/ google/xls/blob/main/xls/dev tools/check ir equivalence main.cc, 2024, accessed: 2025-09-08. [29] Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, and P. Martineau, “A parallel graph edit distance algorithm,” Expert Systems with Applications, vol. 94, pp. 41–57, 2018. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S095741741730725X [30] D. B. Blumenthal, S. Bougleux, J. Gamper, and L. Brun, “Gedlib: A c++ library for graph edit distance computation,” in Graph-Based Representations in Pattern Recognition, D. Conte, J.-Y. Ramel, and P. Foggia, Eds. Cham: Springer International Publishing, 2019, pp. 14–24. [31] C. Piao, T. Xu, X. Sun, Y. Rong, K. Zhao, and H. Cheng, “Computing graph edit distance via neural graph matching,” Proc. VLDB Endow., vol. 16, no. 8, p. 1817–1829, Apr. 2023. [Online]. Available: https://doi.org/10.14778/3594512.3594514 [32] E. Jain, I. Roy, S. Meher, S. Chakrabarti, and A. De, “Graph Edit Distance with General Costs Using Neural Set Divergence,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [Online]. Available: https://openreview.net/forum?id= u7JRmrGutT [33] R. Wang, T. Zhang, T. Yu, J. Yan, and X. Yang, “Combinatorial learning of graph edit distance via dynamic embedding,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2021, pp. 5241–5250.
10