Patent ID: 12229482

DETAILED DESCRIPTION

With reference toFIGS.1and2, an electronic processor10is programmed by instructions stored on a non-transitory storage medium12to perform a Register Transfer Level (RTL) representation recovery method. Said another way, the non-transitory storage medium12stores instructions which are readable and executable by the electronic processor10to perform the RTL representation recovery method. The illustrative electronic processor10comprises a desktop or notebook computer. More generally, the electronic processor10may be a desktop computer, server computer, cluster of server computers, cloud computing resource comprising an ad hoc network of computers, or so forth. The non-transitory storage medium may be: a hard disk drive (optionally internal to the computer10) or other magnetic storage medium; a solid state drive (SSD), flash memory, or other electronic storage medium; an optical disk/drive or other optical storage medium; various combinations thereof, or the like. A display14is operatively connected with the electronic processor10to display results generated by the RTL representation recovery method. These results may, for example, include a listing of the RTL representation (or a selected portion thereof) in a Hardware Description Language, and/or test results comprising outputs generated by the RTL representation for chosen test inputs. One or more user input devices, such as an illustrative keyboard16, mouse18, touch-sensitive overlay of the display14, various combinations thereof, and/or so forth are provided via which a user interacts with the RTL representation recovery method, for example by operating a graphical user interface (GUI) via which a netlist20is provided as input to the RTL representation recovery method (whereby the RTL representation recovery method generates an RTL representation of the netlist) and/or via which the user selects a portion of the RTL representation to view on the display14or so forth.

The netlist20which serves as input to the RTL representation recovery method may be generated in various ways. In general, it is assumed that the original RTL from which the netlist was generated is unavailable (which is why the RTL representation recovery method is being applied). Rather, in the case of an FPGA the netlist20may be reverse engineered based on outputs generated by the FPGA in response to test inputs. See, e.g., Benz et al., “BIL: A Tool-Chain for Bitstream Reverse-Engineering”, 22nd International Conference on Field Programmable Logic and Applications (FPL) (Aug. 29-31, 2012); Ding et al., “Deriving an NCD file from an FPGA bitstream: Methodology, architecture and evaluation”, Microprocessors and Microsystems vol. 37, pp. 299-312 (2013); Jean-Baptist Note & Eric Rannaud, “From the bitstream to the netlist”, in Proc. of the 16th International ACM/SIGDA Symposium on Field Programmable Gate Arrays”, Monterey, California, Feb. 24-26, 2008. In the case of an ASIC, the netlist20may be generated by scanning electron microscope (SEM) imaging and/or other forensic analysis of the ASIC, optionally along with analysis of outputs generated by the ASIC in response to test inputs. The netlist20is typically a flat netlist without a hierarchy.

With brief reference toFIG.3, an illustrative netlist201for a 2-bit counter is shown, along with a corresponding RTL representation22. As seen inFIG.3, the netlist is a text file that lists electronic components and their connections. It is a flat list, with no hierarchy, and provides no information about component functionality. It only contains the connectivity of the most primitive and fundamental circuit blocks (e.g. NAND, NOR, INV, DFF, etc. gates) The RTL representation is also a text file, in a HDL, specifically employing the IEEE 1164 VHDL standard in the illustrative RTL22. The RTL representation is a high level hierarchical functional description.

With reference back toFIG.1, the RTL representation recovery method starts with text parsing and pruning operations30to pre-process the netlist20. This may entail, for example, removing comments, headers, and other extraneous information in the netlist20. The preprocessing resolves any portions that would not be recognized as syntactically valid Verilog (or other employed HDL). Some manual preprocessing of the netlist is contemplated.

With continuing reference toFIG.1and further reference toFIGS.4and5, the preprocessed netlist is then converted into a multi-typed graph. To achieve this, in an operation34the preprocessed netlist is converted to an Abstract Syntax Tree (AST)36.FIG.4presents an illustrative example of a preprocessed netlist202and corresponding AST362. In this illustrative example, the root of the AST is the “Netlist” node, from which the “Timescale” and “Module” nodes branch, with the components and their connections being represented by nodes branching off the “Module” node. The AST36is then converted in an operation38to a multi-typed graph40.FIG.5shows an illustrative typing ontology for the multi-typed graph40, which includes a set of node types including: an instance node type representing an electronic component; a wire node type representing signal transfer between components; an input node type representing an input terminal of the netlist; an output node type representing an output terminal of the netlist; and a constant node type representing a constant signal source (e.g., Vccor ground, or alternatively logical “1” or logical “0”, or another suitable representation of the constant values of a binary system).

The instance node type represents a component that performs an operation on one or more input signals and drives an output signal. Typically, an instance node has one or more input signals and a single output signal (although two or more outputs from a node of the instance node type is also contemplated). For example, an AND gate may be represented by an instance node with two (or more) input signals and a single output signal whose value is the logical AND of the two (or more) input signals. As another example, an instance node representing a buffer has a single input signal and a single output signal whose value is equal to that of the input signal. An instance node representing a LUT has one or more input signals and an output signal corresponding to the output of the LUT for the input signal(s). An instance node representing a flip-flop (FF) has one or more inputs and an output whose value depends on the inputs and on an internal state of the FF.

The wire node type has a single input signal and one or more output signals, with the value of each output signal being equal to the value of the single input signal. The wire node thus efficiently captures the possibility of a signal being fed into multiple other components by way of a single node of the wire node type. In this way, the wire nodes can later be directly converted to signal declarations in the RTL, followed by signal assignments obtained from the wire node connections to instance nodes.

With continuing reference toFIG.1and with further reference toFIGS.6and7, in the operation38, the graph40is generated from the AST36by stepping through the tree representation and generating lists of node names of the various node types as the AST36is traversed. For components and signals designated by standard nomenclature, the directionality of edges connecting nodes of the graph40are assigned. However, some nodes or signals may employ manufacture-specific nomenclature such that directionality cannot be determined from the AST36alone—these ambiguities will be resolved in the next stage. The AST36is a data structure that provides a list of the netlist's components and connections between them in a way that is easily traversable. The graph40is created by instantiating each component listed in the AST36as a node in the graph and creating connections between these nodes based on connection information from the AST. By way of non-limiting illustrative example,FIG.6illustrates a graph for a simple two-input logic gate (e.g., a 2-input AND gate, 2-input OR gate, or so forth). In general, each pair of nodes from the group consisting of instance nodes, terminal nodes, and constant nodes are interconnected by way of an intervening wire node. This, again, facilitates conversion of the wire nodes to RTL signal declarations later in the RTL recovery process.FIG.7shows a diagrammatic representation of a graph for a 32-bit single precision Floating Point Unit (FPU) from RISC Processor (5 stage pipeline). The graph ofFIG.7shows the nodes as points without distinguishing the node type, but illustrates the high degree of complexity of the graph representation of the netlist for a more complex IC design and shows that there is inherent hierarchy that can be observed in the flattened netlist when observed in this way.

With continuing reference toFIG.1and with further reference toFIG.8, the operation38preferably further includes graph pruning to remove unused or redundant nodes, such as unconnected devices, buffers, LUTs acting as buffers, double inverters, doubly-connected wires, or so forth. Processing time and graph readability can be improved by such pruning.FIG.8illustrates two examples of pruning operations: removal of a redundant wire (left-hand diagram), and removal of a redundant buffer (right-hand diagram).

The resulting graph40advantageously captures the components and connections of the netlist20in a format that is more readily converted to RTL as described herein. For components and signals designated by standard nomenclature, the directionality of edges connecting nodes of the graph40are assigned in the operation38. However, some nodes or signals may employ manufacture-specific nomenclature (that is, the node and signal nomenclature may be specific to the IC manufacturer). In such cases, directionality cannot be determined at operation38. Similarly, different manufacturers and device families use different primitives. Functionality of primitives by different manufacturers may be identical, but port information and primitive names typically vary.

Thus, with continuing reference toFIG.1and with further reference toFIG.9, in an operation42, node standardization is performed. This entails replacing nodes of the graph40with standardized nodes using an IC nomenclature database44.FIG.9shows an example of this operation42. In general, the nodes may employ manufacturer-specific naming conventions, for which port (and hence graph edge) directionality is unknown, and functionality of the instance nodes is unspecified. This is diagrammatically shown by two examples of nodes with manufacturer-specific nomenclature (top two diagrams ofFIG.9with node names “GFG LUT3-L” and “X_LUT3” respectively, and manufacturer-specific signal names as shown in the top diagrams ofFIG.9). The IC nomenclature database44provides this manufacturer-specific nomenclature so as to resolve these manufacturer-specific node and signal names to standardized names (e.g., the top diagram nodes ofFIG.9are resolved to the standardized node named “LUT_3”, with standardized signal names as shown in the bottom diagram ofFIG.9. Additionally, the resolution of the node “LUT_3” (or more generally, replacement of a manufacture-specific node with an equivalent standardized node) allows the directionality of the node ports to be resolved. Hence, the output of operation42is a fully directed graph.

With continuing reference toFIG.1and with further reference toFIG.10, in an operation46, LUTs and primitives are decomposed. In general, higher-level components such as LUTs and higher level primitives compress structural information and make pattern recognition and structural identification more difficult. In the case of primitives, the IC nomenclature and primitives database44may be referenced to identify manufacturer-specific primitives and their decomposed equivalents consisting of logic gates and FFs (and possibly also LUTs). To decompose a LUT, a process as shown inFIG.10is suitably employed. The LUT initialization vectors (which define the LUT output for any combination of inputs) is represented as a truth table having columns corresponding to the inputs and a final column corresponding to the LUT output. The truth table is expanded into an equivalent simplified Boolean expression that is minimized by standard minimization techniques such as identifying and merging groups of inputs with a common output value. The simplified Boolean expression is then represented as a subgraph with instance nodes representing the logic gates of the Boolean expression. A subgraph that includes a LUT node is thereby replaced with a standardized subgraph that does not include a LUT node. It should be noted that the illustrative LUT decomposition ofFIG.10is for an FPGA. In the case of an ASIC, LUT decomposition is typically not performed; whereas, for an FPGA the LUT decomposition facilitates obtaining a useful graph from the netlist. More generally, higher-order functionality can typically be recovered more quickly from an FPGA netlist (as compared with an ASIC) when onboard hardware of the FPGA cells (such as adders or multipliers) is used instead of synthesizing this functionality into logic cells.

The output of the operation46is a standardized graph50, which is a fully directed graph and which employs standardized nomenclature, and which has LUTs and higher level primitives decomposed into subgraphs consisting of logic gate instance nodes and (usually) FF instance nodes. The standardized graph50consists of basic logic nodes (e.g. AND, OR, NOT) and FF nodes, in addition to input and output terminal nodes and constant signal source nodes (seeFIG.5).

With reference toFIG.2, the standardized graph50is used to recover the RTL representation of the netlist20. The structure of the standardized graph50lends itself well to creating an RTL representation in VHDL code or another HDL such as Verilog or SystemVerilog, as each wire node is analogous to a VHDL ‘signal’ (or, equivalently, a Verilog or SystemVerilog ‘signal’), as it has one driver and unlimited outputs (that is, a single input signal and one or more output signals, wherein the value of each output signal is equal to the value of the single input signal). Hence, an operation60builds VHDL signal declarations from the wire nodes of the standardized graph50. That is, signals are declared for each wire node. An operation62builds signal assignments from instance nodes. Signal states are assigned to logical operations on other signals and design inputs.

However, some standard cells and FPGA primitives do not have simple gate-level equivalents. Some examples include: multiplication stages, RAM, ROM, or so forth. The use of these primitives is useful for determining hierarchy, but is not advantageous for simulation. Additionally, many slight variations of simple components like flop-flops exist, e.g. active high vs active low, bus width, inclusion of set/reset ports, a/synchronous set/reset, and so forth.

To address these situations, an operation64defines synchronous devices from templates. In an illustrative embodiment, rather than code simulation primitives for every case, a modular template system is employed, which makes use of a template VHDL library66of VHDL ‘Generics’ and enables or disables functionality as appropriate for a given standard cell or FPGA primitive. The information from the template VHDL library66is stored in nodes during classification. A component-to-template map68provides manufacturer- or device family-specific information as to the modifications to the VHDL template standard cell or FPGA primitive appropriate for the specific IC whose RTL representation is being recovered. An operation70instantiates and connects the synchronous logic. Each node corresponding to a standard cell or FPGA primitive in the standardized graph50is represented in the VHDL code by an instance of the synchronous device primitive defined in the operation64, with connections to the surrounding circuitry of that node in the standardized graph50. This introduces some hierarchy into the RTL representation. An operation72then introduces (further) hierarchy to the RTL for repeated structures. An operation74writes the RTL to a VHDL file76, thus completing the RTL recovery process. It should be noted that while VHDL is employed inFIG.2as an illustrative Hardware Description Language (HDL), the RTL may be coded in accord with another HDL such as Verilog or SystemVerilog by employing the appropriate Declarations notation for the chosen HDL in coding operations60,62and a template library and mapping for the chosen HDL in place of the illustrative template VHDL library66and mapping68, respectively.

With continuing reference toFIG.2and with further reference toFIGS.11-13, the operation72introducing (further) hierarchy to the RTL for repeated structures can be implemented in various ways. The structure of the standardized graph50lends itself well to structural identification of components. Identified repeated structures can be replaced by a single higher-level structural declaration in the HDL, and then instances of the structure can be replaced by instantiations of the declared higher level structure.FIG.11illustrates an example of this approach, in which a graph of an 8-bit counter is identified (i.e. matched) as a sub-graph of a graph of a Central Processing Unit (CPU) integrated circuit. It is particularly noteworthy here that the 8-bit counter graph includes an outer loop of flip-flop dependencies (shown in darker lines in the graph for the 8-bit counter. This graph topological feature can be leveraged in identifying the 8-bit counter sub-graph in the CPU graph (sub-graph depicted in lighter lines in the lower right diagram ofFIG.11).

With continuing reference toFIG.2and with further reference toFIG.12, another way to leverage the standardized graph50for identifying hierarchical structures in the operation72is by way of simulation. Combinational logic processing can be simulated by assigning signal values to selected wire nodes and simulating the result. In this way, components such as adders can be identified by simulating combinational logic chunks between flip-flops. More generally, frequent patterns identified from graph mining can be simulated and compared to a list of known components. Again, identifying flip-flop interdependencies can be useful in identifying repeated patterns.FIG.12illustrates a flowchart of a method80for identifying flip-flop dependencies, which can be used to create a reduced graph82of flip-flop interdependencies for the pattern mining. The reduced graph82produced by the method80contains each flip-flop in the netlist represented as a vertex. The logical path from each flip-flop to the others (if one exists) is represented as an edge. The reduced graph82of flip-flop dependencies is useful for reducing the computation required to identify patterns such as state machines. For example, as previously noted the 8-bit counter ofFIG.11can be identified by searching for the circular dependencies of the eight flip-flops of the counter. The method80ofFIG.12would advantageously provide a reduced graph82isolating these flip-flop interdependencies. More generally, state machines contain a set of flip-flops with outputs that feedback through combinatorial logic to the flip-flop inputs. The combinatorial logic in the feedback path along with the state machine inputs make up the next state expression. The reduced flip-flop graph82can be used with graph searching techniques to quickly identify the sets of flip-flops that meet these criteria.

With continuing reference toFIGS.2and12and with further references toFIG.13, using the reduced flip-flop graph output by the method ofFIG.12, a strongly connected components search can be performed that, in the directed graph (i.e. edges between vertices of the reduced graph of flip-flop dependencies have directionality), will identify all sets of flip-flops that collectively feedback to each other. These flip-flops, in many cases, combine to make up memory that stores the state variables of a state machine.FIG.13illustrates a flow diagram of a method for state machine extraction from an ASIC netlist20according to this approach. (Note, inFIG.13flip-flops are referred to as “registers”). InFIG.13, the processing described with reference toFIG.1for producing the standardized graph50shown in the left branch ofFIG.13is represented inFIG.13by blocks90,92, while the process80for producing the reduced graph82of flip-flop (i.e. register) dependencies is shown in the right branch ofFIG.13. Operation94is the “strongly connected components” search. A loop96selects strongly connected components with between 1 and 100 component vertices in the reduced flip-flop graph82as possible state machines. (This range of 1-100 is merely illustrative, and may be tuned to maximize performance for a particular family of ICs undergoing RTL recovery). For each possible state machine (i.e. each sub-graph of the reduced graph82), a process98retrieves the corresponding sub-graph of the standardized graph50(this sub-graph will include the interconnecting combinational logic of the possible state machine), generates the state transition tables for the sub-graph of the standardized graph50, and produces behavioral-level HDL code representing the state transition tables.

The illustrative RTL recovery methods can be incorporated into various types of IC analysis tools. For example, with reference back toFIGS.1and2, a graphical user interface (GUI) may be provided via which the netlist20is provided as input to the RTL representation recovery method, for example by selecting a text file containing the netlist using the mouse18to navigate a file manager to select the netlist file. The RTL representation recovery method then generates the RTL representation76of the netlist, and the user selects a portion of the RTL representation76to view on the display14. If IC performance simulation software is also provided, the user may perform simulations on the netlist20and the RTL representation76to verify that they exhibit the same functionality. An extracted netlist from an IC could range from tens of thousands of lines long for a simple design up to several million lines for a reasonably complex design. As such, navigating through the flat netlist to identify areas of assurance concern is not practical for a human to perform. Understanding the functionality or locating portions of the design is also not realistic or feasible. By representing the netlist with as recovered RTL with hierarchy and in a more condensed and readable format, a user can more readily identify and understand the regions of interest to determine if the design was modified to alter design functionality. In another application, engineers who are addressing legacy part problems may need to extract the design in order to remanufacture it into a modern technology node. For example, a design that was fabricated in a 500 nanometer technology node, an obsolete technology not readily available today, could be fabricated in a 90 or 45 nanometer technology. In order to perform this, an RTL representation of the design is obtained using the disclosed RTL recovery in order for the designer to resynthesize into the modern node size. A netlist typically cannot be remanufactured; hence the extracted legacy netlist is generally not sufficient to remanufacture the IC. By contrast, the disclosed RTL recovery allows the legacy netlist to be converted into a format that permits resynthesizing into the modern node, thus saving large amounts of resources on a complete redesign of the component.

The preferred embodiments have been illustrated and described. Obviously, modifications and alterations will occur to others upon reading and understanding the preceding detailed description. It is intended that the invention be construed as including all such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof.