Perl Part II · Module 20 · Netlist Processing
Building the Hierarchy Map
Once every instance carries the module it sits in, the flat list becomes a tree, and the tree answers the questions people actually ask: where does this block live, what is inside it, how many cells does it really contain. The last of those is the one worth being careful about, because a hierarchical netlist's text count and its instance count are different numbers — and this chapter establishes the difference three separate ways, the last of them by asking the simulator rather than trusting the script.
Advanced15 min readPerlPart IINetlists
Part II · Module 20 · Chapter 20.4 · Building the Hierarchy Map
1. Parent To Children
The scan already records each instance's enclosing module, so the map is one line — Chapter 7.7's hash of arrays:
push @{ $children{ $_->{parent} } }, $_ for @$inst;The only real decision is telling a sub-module from a leaf cell, and the netlist answers it: a type that appears as a module declaration in this file is a sub-module; anything else is a library cell.
my %IS_MODULE = map { $_ => 1 } @$mods;
...
my $kind = $IS_MODULE{ $c->{type} } ? "module" : "cell";That test is local and reliable, with one caveat worth stating: it is only true for this file. A netlist split across several files, or one whose sub-blocks come from a separate library file, will call a sub-module a cell because its declaration is not here. If the netlist arrives as several files, read them all before building the map.
use strict;
use warnings;
my @KEYWORDS = qw(module endmodule input output inout wire reg assign
parameter localparam always initial generate endgenerate
genvar begin end supply0 supply1);
my %IS_KW = map { $_ => 1 } @KEYWORDS;
sub read_netlist {
my ($file) = @_;
open my $fh, "<", $file or die "$file: $!";
my (@mods, @inst, $cur, $buf, $in_block);
while (my $raw = <$fh>) {
my $l = $raw;
if ($in_block) { if ($l =~ s{.*?\*/}{}) { $in_block = 0 } else { next } }
$l =~ s{/\*.*?\*/}{}g;
if ($l =~ s{/\*.*$}{}) { $in_block = 1 }
$l =~ s{//.*$}{};
next unless $l =~ /\S/;
if ($l =~ /^\s*module\s+(\w+)/) { push @mods, $1; $cur = $1; $buf = ""; next }
if ($l =~ /^\s*endmodule\b/) { undef $cur; $buf = ""; next }
next unless defined $cur;
$buf .= " $l";
next unless $buf =~ /;/;
my $stmt = $buf; $buf = "";
$stmt =~ s/;.*$//; $stmt =~ s/\s+/ /g; $stmt =~ s/^ | $//g;
next unless $stmt =~ /^(\w+)\s+(\w+)\s*\((.*)\)$/;
next if $IS_KW{$1};
push @inst, { type => $1, name => $2, parent => $cur };
}
close $fh;
return (\@mods, \@inst);
}
my ($mods, $inst) = read_netlist("netlist/counter_syn.v");
my %IS_MODULE = map { $_ => 1 } @$mods;
# ---- parent -> children, and which children are sub-modules vs leaf cells
my %children;
push @{ $children{ $_->{parent} } }, $_ for @$inst;
printf "modules declared: %s\n", join(", ", @$mods);
printf "instantiations in the text: %d\n\n", scalar @$inst;
# ---- the TOP module is one that is declared but never instantiated
my %instantiated = map { $_->{type} => 1 } @$inst;
my @tops = grep { !$instantiated{$_} } @$mods;
printf "modules never instantiated (the top): %s\n", join(", ", @tops);
printf "modules used as a sub-block: %s\n\n",
join(", ", grep { $instantiated{$_} && $IS_MODULE{$_} } @$mods);
# ---- print the tree
sub tree {
my ($mod, $depth, $seen) = @_;
$seen ||= {};
if ($seen->{$mod}) { printf "%s%s <-- CYCLE\n", " " x $depth, $mod; return }
local $seen->{$mod} = 1;
for my $c (@{ $children{$mod} || [] }) {
my $kind = $IS_MODULE{ $c->{type} } ? "module" : "cell";
printf "%s%-14s %-12s (%s)\n", " " x $depth, $c->{name}, $c->{type}, $kind;
tree($c->{type}, $depth + 1, $seen) if $IS_MODULE{ $c->{type} };
}
}
for my $t (@tops) {
print "$t\n";
tree($t, 1);
}
# ---- elaborated counts: recursive expansion
sub count_recursive {
my ($mod) = @_;
my ($cells, $insts) = (0, 0);
for my $c (@{ $children{$mod} || [] }) {
$insts++;
if ($IS_MODULE{ $c->{type} }) {
my ($sc, $si) = count_recursive($c->{type});
$cells += $sc; $insts += $si;
} else { $cells++ }
}
return ($cells, $insts);
}
# ---- and an INDEPENDENT iterative expansion, as a cross-check
sub count_iterative {
my ($top) = @_;
my @stack = ($top);
my ($cells, $insts) = (0, 0);
while (@stack) {
my $mod = pop @stack;
for my $c (@{ $children{$mod} || [] }) {
$insts++;
if ($IS_MODULE{ $c->{type} }) { push @stack, $c->{type} }
else { $cells++ }
}
}
return ($cells, $insts);
}
print "\n";
for my $t (@tops) {
my ($cr, $ir) = count_recursive($t);
my ($ci, $ii) = count_iterative($t);
printf "elaborated under %s:\n", $t;
printf " leaf CELLS recursive=%-4d iterative=%-4d agree? %s\n",
$cr, $ci, ($cr == $ci ? "yes" : "NO");
printf " all INSTANCES recursive=%-4d iterative=%-4d agree? %s\n",
$ir, $ii, ($ir == $ii ? "yes" : "NO");
printf "\n the text held %d instantiations; the elaborated design has %d\n",
scalar @$inst, $ir;
printf " ratio: %.2fx -- counting the TEXT undercounts the DESIGN\n",
$ir / scalar @$inst;
}
# ---- instance count per sub-block, which is the question people ask
print "\ninstances inside each module (one level, and elaborated):\n";
for my $m (@$mods) {
my $direct = scalar @{ $children{$m} || [] };
my ($cells, $all) = count_recursive($m);
printf " %-14s direct=%-4d elaborated cells=%-4d\n", $m, $direct, $cells;
}
# ---- a THIRD, independent count: ask the simulator.
# $dumpvars(0, dut) writes one VCD $scope per elaborated module instance,
# so counting them is the tool's own answer to "how many instances".
print "\ncross-check against the simulator (VCD scopes):\n";
my $log = `iverilog -o hd.vvp lib/cells.v netlist/counter_syn.v tb/tb_dump.v 2>&1`;
if (($? >> 8) != 0) {
printf " could not build: %s\n", ((grep { /\S/ } split /\n/, $log)[0] // "");
} else {
system("vvp hd.vvp > /dev/null 2>&1");
my $scopes = 0;
if (open my $v, "<", "h.vcd") {
while (my $l = <$v>) { $scopes++ if $l =~ /^\$scope module/ }
close $v;
}
# the dump contains the testbench scope and the dut scope as well
my $under_dut = $scopes - 2;
my ($cells, $insts) = count_recursive("counter_top");
printf " VCD \$scope module entries: %d\n", $scopes;
printf " minus the testbench and dut scopes: %d instances under counter_top\n", $under_dut;
printf " my recursive expansion said: %d\n", $insts;
printf " do the TOOL and the SCRIPT agree? %s\n",
($under_dut == $insts ? "YES" : "NO -- investigate");
}modules declared: counter_bit, counter_top
instantiations in the text: 18
modules never instantiated (the top): counter_top
modules used as a sub-block: counter_bit
counter_top
clk_gate CKLNQD1 (cell)
clk_buf CKBD1 (cell)
U20 INVD1 (cell)
bit0 counter_bit (module)
U1 INVD1 (cell)
U2 INVD1 (cell)
state_reg DFCNQD1 (cell)
U21 XOR2D1 (cell)
bit1 counter_bit (module)
U1 INVD1 (cell)
U2 INVD1 (cell)
state_reg DFCNQD1 (cell)
U22 AN2D1 (cell)
U23 XOR2D1 (cell)
bit2 counter_bit (module)
U1 INVD1 (cell)
U2 INVD1 (cell)
state_reg DFCNQD1 (cell)
U24 AN2D1 (cell)
U25 XOR2D1 (cell)
bit3 counter_bit (module)
U1 INVD1 (cell)
U2 INVD1 (cell)
state_reg DFCNQD1 (cell)
U26 BUFFD1 (cell)
U27 TIELO (cell)
FILLER_1 FILL1 (cell)
elaborated under counter_top:
leaf CELLS recursive=23 iterative=23 agree? yes
all INSTANCES recursive=27 iterative=27 agree? yes
the text held 18 instantiations; the elaborated design has 27
ratio: 1.50x -- counting the TEXT undercounts the DESIGN
instances inside each module (one level, and elaborated):
counter_bit direct=3 elaborated cells=3
counter_top direct=15 elaborated cells=23
cross-check against the simulator (VCD scopes):
VCD $scope module entries: 29
minus the testbench and dut scopes: 27 instances under counter_top
my recursive expansion said: 27
do the TOOL and the SCRIPT agree? YES2. The Tree, And Finding The Top
The printed tree is the useful artefact: counter_top holding eleven leaf cells and four counter_bit blocks, each of those holding two inverters and a flop.
Finding the top module needs no configuration. The top is the module that is declared and never instantiated:
my %instantiated = map { $_->{type} => 1 } @$inst;
my @tops = grep { !$instantiated{$_} } @$mods;Measured: counter_top. That is a better answer than taking the top from a command-line argument or guessing by filename, and it generalises — the same test finds the top of a netlist you have never seen.
Two things it also tells you, for free:
More than one top means something. Either the netlist genuinely contains several unrelated blocks, or a module you expected to be instantiated is not — a block that got optimised away, or one whose instantiation is in a file you did not read.
No top at all means a cycle. Every module is instantiated by something, which in a netlist is impossible, so the structure is wrong. Section 5 is about that.
3. Text Count Versus Elaborated Count
Figure 20.4.1 — Why the text count is not the design count
The measurement:
the text held 18 instantiations; the elaborated design has 27
ratio: 1.50x -- counting the TEXT undercounts the DESIGNOne level of hierarchy and four repeats is enough to make the text count wrong by half. And the ratio is unbounded: a block instantiated sixty-four times contributes sixty-four copies of its contents while adding nothing to the file's length.
So the two questions have to be asked separately, which is the discipline Chapter 20.2 introduced and this chapter quantifies:
"How many DFCNQD1 lines are in this file?" — a text question. One flop line appears in counter_bit.
"How many flops are in this design?" — an elaboration question. Four, because counter_bit is instantiated four times.
Chapter 20.5's census counts text. It is a design census only when the netlist is fully flattened, and the hierarchy map built here is what converts one into the other.
4. Three Counts That Agree
A single implementation that produces 27 proves nothing — it proves 27 is what my code computes. So the script computes it three ways.
A recursive expansion, descending into each sub-module and summing.
An iterative expansion, written separately with an explicit stack rather than the call stack. It shares no code with the recursive version, so a misconception in one is unlikely to be present in the other.
The simulator's own hierarchy. $dumpvars(0, dut) writes one VCD $scope module entry per elaborated module instance, and counting them asks the tool rather than the script:
VCD $scope module entries: 29
minus the testbench and dut scopes: 27 instances under counter_top
my recursive expansion said: 27
do the TOOL and the SCRIPT agree? YESAll three agree on 27, and the first two agree on 23 leaf cells. The third is the one that matters most: two implementations I wrote could share a wrong assumption about what counts as an instance, and the simulator's elaborated hierarchy cannot. Chapter 18.10 put the general rule as needing an instrument that could have disagreed; a tool with its own opinion is the best available version of that.
5. The Cycle Guard
A netlist cannot contain a cycle — a module cannot instantiate itself, directly or through a chain — so a cycle in the map means the input is wrong or the scan misread it.
The guard matters because of what happens without it. The tree printer is recursive (Chapter 10.9), so a cycle is infinite descent, not a wrong answer. The same point Chapter 19.5 made about the dependency sort: the check has to be there before you need it, because its absence does not produce a bad result, it produces a hang.
if ($seen->{$mod}) { printf "%s%s <-- CYCLE\n", " " x $depth, $mod; return }Measured here the tree prints normally and no cycle is reported, which is the expected result on a valid netlist — and the branch is still what stands between a malformed input and a script that never returns.
How a cycle actually arises in practice is worth knowing, since the netlist itself cannot have one:
Two netlist files read together where both define a module of the same name, and the two definitions instantiate each other's version.
A scan that misattributes a parent — an endmodule missed because it followed an unterminated block comment, so the next module's instances are recorded under the previous module.
Both are reasons to report the cycle with the chain, not just to detect it: the chain names the files and modules somebody needs to look at.
6. What To Remember
- A parent-to-children map is one line — a hash of arrays keyed on the enclosing module (7.7).
- A type that appears as a
moduledeclaration in this file is a sub-module; anything else is a cell. - That test is per file. A multi-file netlist must be read in full, or sub-modules are misclassified as cells.
- The top module is the one declared and never instantiated — no configuration needed, and it generalises.
- More than one top means a block was optimised away or a file was not read; no top at all means a cycle.
local $seen->{$mod} = 1restores the flag on the way out, which is what lets one sub-module print under all four parents. Withoutlocal, three of the four would silently print empty.- Measured: 18 instantiations in the text, 27 instances elaborated — 1.50x — with one level of hierarchy and four repeats.
- The ratio is unbounded: a block used 64 times multiplies its contents 64-fold and the file gets no longer.
- "How many lines" and "how many cells in the design" are different questions. Ask them separately.
- A flat per-type census is a design census only on a fully flattened netlist (20.5).
- Measured three ways that agree: recursive expansion, an independent iterative expansion, and the simulator's VCD
$scopecount — 27, 27, 27. - The tool's number is the one that cannot share your misconception — two of your own implementations can.
$dumpvars(0, dut)gives a real elaborated hierarchy, resolving generate blocks and parameters — but it needs the library, a testbench and a licence, and a full-chip VCD is enormous. A cross-check, not a method.- Keep the cycle guard: the printer is recursive, so a cycle hangs rather than fails (10.9, 19.5).
- A cycle means two files defining one module, or a missed
endmodule— report the chain, not just the fact.
Chapter 20.5 counts and classifies. With the hierarchy available, a per-cell-type census can be reported both as written and as elaborated — and the more useful output is not the count but the list of cell types that should not be in the netlist at all.
Where this fits
Part of the Perl curriculum.