Dataflow Analysis

The dataflow analysis (DANA) plugin aims to recover word-level registers from the unstructured sea of gates. It identifies registers by analyzing shared control signals of flip-flops and by leveraging structural information such as register stages. For details on the methodology, see the original DANA paper.

Executing DANA

To execute dataflow analysis in its default configuration for register recovery, run:

from hal_plugins import dataflow

config = dataflow.Configuration(netlist)
config = config.with_flip_flops()

res = dataflow.analyze(config)

Advanced Configuration

You can fine-tune the algorithm by enabling/disabling register stage identification, specifying register sizes most likely to be found within the analyzed netlist (e.g., 32 for a 32-bit CPU), or setting the minimum register size. This is done using the dataflow.Configuration class as follows:

config = dataflow.Configuration(netlist)
config = config.with_flip_flops()
config = config.with_expected_sizes([32, 64])   # set expected register sizes to 32 and 64
config = config.with_min_group_size(4)          # set minimum register size to 4
config = config.with_stage_identification()     # enable register stage identification

res = dataflow.analyze(config)

Please note that registers smaller than the minimum register size may still be output if no larger register could be reconstructed, but will have low priority during the voting that is part of the dataflow analysis. Hence, if a larger register is plausible, it will be preferred by the algorithm.

Known Groups and Structures

To further refine analysis and benefit from potential previous analyses performed on the netlist, both already identified registers and also other word-level structures or gates may be provided to DANA. Previous analysis steps may have already identified, e.g., shift registers, that can now be fed to DANA using config.with_known_groups. If word-level structures such as adders or counters have been identified in combinational logic before, those can be provided to DANA using config.with_known_structures. Both known groups and structures may be provided to DANA in many different forms. Please refer to the official API documentation for details.

config = dataflow.Configuration(netlist)
config = config.with_flip_flops()
...
config = config.with_known_groups(some_list_of_groups)          # provide previously identified register groups
config = config.with_known_structures(some_list_of_structures)  # provide other non-flip-flop word-level structures

res = dataflow.analyze(config)

Beyond Registers

Ever since the publication of the original paper, DANA has been extended to operate not only on flip-flops and their control pins, but also on any user-specified gate type. The function config.with_gate_types() can be used to provide the target gate type and with config.with_control_pin_types() the corresponding control pins can be set. This way, DANA could for example be used to reconstruct word-level multiplexers from individual MUX gates using their select inputs.

config = dataflow.Configuration(netlist)
...
config.with_gate_types({hal_py.GateTypeProperty.c_mux})
config.with_control_pin_types({hal_py.PinType.select})

res = dataflow.analyze(config)
``

Please note that the function `config.with_flip_flops()` is nothing but a short-hand for

```python
config.with_gate_types({hal_py.GateTypeProperty.ff})
config.with_control_pin_types({hal_py.PinType.clock, hal_py.PinType.enable, hal_py.PinType.set, hal_py.PinType.reset})

and will overwrite any previous assignment of gate types or pin types.

Working With the Result

Running dataflow analysis using dataflow.analyze produces an object of class dataflow.Result that enables interaction with its results. It allows access to the register groups and provides a set of utility functions to perform simple operations on the result, as shown below:

res = dataflow.analyze(config)
res.get_groups()                                      # returns all register groups as a dictionary from group ID to a set of the gates contained in the group
res.get_gates_of_group(3)                             # returns all gates belonging to the register group with ID 3
res.get_group_id_of_gate(some_gate)                   # returns the ID of the register group that the given gate belongs to
res.get_group_predecessors(3)                         # returns the predecessor register groups of the group with ID 3 as a set of group IDs
res.get_group_successors(3)                           # returns the successor register groups of the group with ID 3 as a set of group IDs
res.get_group_control_nets(3, hal_py.PinType.clock)   # returns a set of nets connected to the clock input of gates within group with ID 3

Manual modifications can be applied to the result of dataflow analysis by merging or splitting existing register groups.

merged_group = res.merge_groups([3, 4])                 # merges the groups with IDs 3 and 4
split_groups = res.split_group(3, [gates_1, gates_2])   # splits group with ID 3 into a group containing 'gates_1' and another one containing 'gates_2'

Finally, dataflow.Result provides functions to write the results to a file or even merge it into the netlist. All these function take an optional argument that allows to restrict them to only consider selected groups.

res = dataflow.analyze(config)
res.write_txt("some/file/path/result.txt")             # writes a textual representation of the result to the specified file
res.write_dot("some/file/path/graph.dot", {4, 5, 6})   # writes a .dot file describing the dataflow graph, but only includes register groups with IDs 4, 5, and 6 
res.create_modules(group_ids={4, 5, 6})                          # creates modules for the register groups with ID 4, 5, and 6 within the netlist