See also 8. The new netlist scanner as well as 14. A smarter sinks list allocator for the rest.

---

As I try to integrate the Backwards component, I see no place where I could easily change a few lines of code to make it work (although the principle itself is quite simple, right ?). Instead I am facing a big plate of spaghetti, not with the code itself (which is rather good, thanks) but with the data structures that are interwoven and the naming that might not be reflecting the function (which has certainly evolved since their creation). Oh and I didn't log much about the internals, so that genius pile of code is hard to re-architect easily.

Of course there are good and great things that I want to keep. However I see that my initial technique for netlist extraction is quite under-efficient in the case of large designs : it works for small systems but I'm evaluating how it will scale to much larger circuits and I face a O(n²) vs O(n×log(n)) problem. If I ever have one million gates, the setup phase will be ... loooong.

So I have to redesign some parts. This affects only 2 files : VectGen.vhdl and Gates_lib.vhdl, but the data structure depend a lot on the algorithms and I'm going to significantly change the latter. I must re-engineer the former... And this time I must document them ! In essence, I must rewrite just after the first routine :

-- the main sequence of VectGen.vhdl:
GetVectorsSize; -- probing the inputs and outputs
GetNetList;     -- actively probing the gates
FixSinklist;    -- post-processing, no gate activity
FixDepthList;
DisplayDepthList;

GetVectorsSize is alright so far (though it might be re-designed one day, but it's another story).
Edit : see 5. Another method to create the wrapper

GetNetList however is a big offender and needs a replacement, and the change in algorithm could lead to a change in data structures, that will affect the next procedures : FixSinklist and FixDepthList. This is where I can check for "zombies" and/or take Backwards into account. Changing GetNetList will probably lead to the redesign of FixSinklist and others as well...

---

The basic idea is that of drivers and sinks, as anywhere. A net is all the connections between the driver and all the sinks, so the "net" is practically described by the driver (we don't play with tristates here). So a "netlist" is just a list of drivers, with sublists of respective sinks.

But a complete digital circuit must have input ports and output ports, not just logic gates, so the main database is (as already described in 1. First upload):

• A list of gates, each with one output and an array of inputs. The array is indexed with gates numbers >= 1

  Gates_lib.vhdl :
  type Gate_Desc_Array is array(integer range <>) of Gate_Descriptor;
  type Gate_Desc_Access is access Gate_Desc_Array;
  shared variable GateList : Gate_Desc_Access;
  ...
  GateList := new Gate_Desc_Array(1 to gate_instance_counter);

  The size is known after the elaboration phase, after all the gates have called their respective census function, but before the very first clock cycle. update_select_gate must be called by the very first component in the hierarchy list.
  

• A list of input ports, which is an array of  drivers. The std_logic_vector is "downto 0" but the signals are mapped to gates numbers < 1 (range "-x to 0"). Note that these numbers are valid when found in a sink port.

  Gates_lib.vhdl:
  shared variable input_records : output_record_access; 

• A list of output ports, the reverse of the input ports : this is an array of sinks, with positive indexes for the std_logic_vector, but mapped to the negative ( < 1) gate numbers found on drivers.

  Gates_lib.vhdl:
  shared variable output_records : input_records_access;

The port sizes are determined by GetVectorsSize after a number of clock cycles.

-- allocate some memory for the descriptors
output_records := new input_records_array(0 to VectOutMax);
 input_records := new output_record_array(0 to VectInMax);

And this is only now that I realise I shouldn't have called it "input_records_array" but "sink_records_array" because it adds to the confusion...

---

So what are those sinks and drivers, what do they contain and how are they implemented ? In fact there are two versions of the story : the ugly and the tidy:

• The ugly version is when the netlist is being created, with so many unknowns that it's impossible to know any size for sure. The solution is called "linked lists" : the driver has the number to the first sink, which has the number to the second sink, and so on. The link is a small size increase to the gates and all, but this avoids a lot of dynamic allocations and reallocations.
• The tidy version comes after the ugly version is completed. Knowing all the sizes, one array can be dynamically allocated for each net such that random/indexed access is possible and easy. This requires a sort of "compilation" or transformation of the ugly version into the clean one.

The memory footprint must also be carefully considered. To save space, a new compact representation is introduced :

• Driver addresses are a relative number, with numbers above 0 being gates and numbers below 1 being input ports (nothing new here)
• Sink addresses are also a relative number, with numbers below 1 representing output ports. Positive addresses however must encode not only the gate but also the input port number, between 0 and 3. A simple first-order formula encodes both into a single number:

  address := (gate_number * 4) + input_number;
  input_number := address mod 4; -- and 3
  gate_number := address / 4; -- shr 2

  This reduces the coding weight and size vs the previous system where a sink is a record with 2 numbers...
  This also allows the creation of a large (sparse) array to map all the gates inputs.

It's a hack but at least I managed to encode everything in a single integer. Clarity dictates that these addresses should be subtypes of integer, to prevent any confusion and bug. Indeed : you can not directly compare a sink number and a driver number anymore ! The code below is added to Gates_lib.vhdl, it's just added syntax but at least it's not a record and the coding intention is more explicit (there are already so many integers here and there).

type gate_port_number_type is range 0 to 3;
type sink_number_type is range integer'range;
type driver_number_type is range integer'range;

At minimum, sinks only need to point to the driver. The linked list could be temporarily stored in an external array of integ... of numbers.

The drivers must also store the fanout : the number of sinks. There is nothing else that strictly belongs to the driver definition, so a driver is simply a record with 2 fields. The 2nd field is either a pointer to a first sink, or to an array.

The previous version of the code would "recompile" each linked list and allocate a new array, each with it housekeeping data. Considering that the meta-information of the array easily outsizes the contents if the fanout is small (1, 2 or 3 sinks is the majority of the cases), this might not have been the wisest and most efficient (fast and compact) organisation for FixSinklist and others.

All those tiny arrays could be merged into a large vector/array, and the driver contains either:

• The index in the large "gates sinks array" if the fanout is > 1 (and "fanout" following entries are the sub-array)
• The sink number itself if fanout < 1 or when in "linked list" mode.

Both are integer numbers so there is no need to make 2 versions of the record, or a "union" (which VHDL doesn't support).

type driver_record is
  record
    sink_address : integer; -- can be either:
       -- * when fanout > 1 : an index in the unified sinks table
       -- * when fanout < 2 : a sink_number_type
    fanout : integer;
  end record;

This already reduces the complexity and confusion created by the previous input_address_record and input_record_type.

---

I mentioned a large array of sink_number_type and in first approximation, the size could be gate_instance_counter*4. Let's not forget the output ports, of course. But that number can be refined to a more accurate value because gate_instance_counter is computed with all the calls to the census functions and they can be extended with an argument, which is the inputs count. Then, when GetVectorsSize returns, it is easy to allocate the right amount of memory. Because, you know, when you have to deal with a million gates, this is the kind of detail that starts to matter.

shared variable total_sinks_count : integer := 0;
...
impure function Gate_Census(sinks: integer) return integer;

Of course this breaks the PA3_gategen.vhdl code, which is now updated as well...

---

To complete the picture, here is the (partial) definition of a gate :

type Gate_Descriptor is
  record
    -- general info:
    gate_kind  : enum_gate_kind; -- boolean, DFF or backwards ?
    gatename   : line;           -- full path & name of the gate
    -- Lookup & histograms :
     .....
    -- for the probe:
    sinks    : sink_number_array(0 to 3);
    driver   : driver_record;
  end record;

The initial netlist is made of:

shared variable GateList : Gate_Desc_Access;  -- The array that contains all the gates
shared variable sinks_lists, -- dynamic array with total_sinks_count entries, essential part of the netlist
       output_sinks : sink_number_array_ptr; -- the dynamic array of descriptors of the output port
shared variable input_drivers : driver_record_array_access; -- array of the descriptors of the input port

You see the first mention of sinks_list, the main array that contains the lists of sinks (with the index and length given by the driver records).

It is complemented by global variables for the size of each array:

GateList       => gate_instance_counter
sinks_lists    => total_sinks_count
output_sinks   => VectOutMax
input_drivers  => VectInMax
indexPtr       => registered_instance_counter

By the way : indexPtr is simply an array of gate numbers that have more than 1 input and where it is worth it to collect the histogram data (it's a subset of the GateList but the eventual confusion is worth clearing).

....

Continued at 8. The new netlist scanner