Compile Order and Package Dependencies

Part II · Module 19 · Chapter 19.5 · Compile Order and Package Dependencies

1. What Each File Defines, And What It Needs

Two questions per file, both answerable with an anchored pattern:

• What does it define? A package or an interface declares a name other files can import.
• What does it need? An import names a package that must already exist.

use strict;
use warnings;

my @FILES = qw(rtl/core/alu.sv rtl/core/chip_pkg.sv rtl/core/counter.sv
               rtl/core/types_pkg.sv tb/tb_counter.sv);

# ---- 1. read each file: what does it DEFINE, what does it NEED?
my (%defines, %needs);
for my $f (@FILES) {
    open my $fh, "<", $f or die "$f: $!";
    while (my $l = <$fh>) {
        $defines{$f}{$1} = 1 if $l =~ /^\s*package\s+(\w+)\s*;/;
        $defines{$f}{$1} = 1 if $l =~ /^\s*interface\s+(\w+)\b/;
        $needs{$f}{$1}   = 1 if $l =~ /^\s*import\s+(\w+)\s*::/;
    }
    close $fh;
}
printf "%-26s %-22s %s\n", "FILE", "DEFINES", "NEEDS";
for my $f (@FILES) {
    printf "%-26s %-22s %s\n", $f,
        (join(",", sort keys %{ $defines{$f} // {} }) || "-"),
        (join(",", sort keys %{ $needs{$f}   // {} }) || "-");
}

# ---- 2. who provides each name?
my %provider;
for my $f (@FILES) { $provider{$_} = $f for keys %{ $defines{$f} // {} } }

# ---- 3. topological order: a file comes after everything it needs
my (%state, @order, @cycle);
sub visit {
    my ($f, @path) = @_;
    return if ($state{$f} // "") eq "done";
    if (($state{$f} // "") eq "open") { push @cycle, join(" -> ", @path, $f); return }
    $state{$f} = "open";
    for my $name (sort keys %{ $needs{$f} // {} }) {
        my $dep = $provider{$name};
        next unless defined $dep && $dep ne $f;
        visit($dep, @path, $f);
    }
    $state{$f} = "done";
    push @order, $f;
}
visit($_) for @FILES;

print "\ntopological order:\n";
printf "  %d. %s\n", $_ + 1, $order[$_] for 0 .. $#order;
printf "cycles detected: %s\n", (@cycle ? join("; ", @cycle) : "none");

# ---- 4. hand several orders to the compiler
sub build {
    my ($label, @list) = @_;
    open my $o, ">", "o.f" or die $!;
    print $o "$_\n" for @list;
    close $o;
    my $log = `iverilog -g2012 -I rtl/include -o /dev/null -c o.f 2>&1`;
    my $rc  = $? >> 8;
    my ($first) = grep { /\S/ } split /\n/, ($log // "");
    printf "  %-30s rc=%-3s %s\n", $label, $rc,
        ($rc == 0 ? "compiles" : ($first // "failed"));
    return $rc;
}

print "\nhand each ordering to the compiler:\n";
build("topological (derived)",      @order);
build("alphabetical by path",       sort @FILES);
build("reverse alphabetical",       reverse sort @FILES);
build("directory walk order",       @FILES);
build("packages last",              (grep { !/_pkg\.sv$/ } @FILES), (grep { /_pkg\.sv$/ } @FILES));

# ---- 5. is alphabetical order just luck?
print "\nis alphabetical order reliable, or lucky here?\n";
my @alpha = sort @FILES;
my %pos; @pos{@alpha} = (0 .. $#alpha);
my @violations;
for my $f (@FILES) {
    for my $name (sort keys %{ $needs{$f} // {} }) {
        my $dep = $provider{$name} or next;
        push @violations, "$f needs $name from $dep, which sorts AFTER it"
            if $pos{$dep} > $pos{$f};
    }
}
printf "  alphabetical order violates %d dependency(ies)%s\n",
    scalar @violations, (@violations ? ":" : " -- it happens to work here");
printf "    %s\n", $_ for @violations;
print "  rename chip_pkg.sv to zz_chip_pkg.sv and alphabetical breaks;\n";
print "  the topological order does not depend on the spelling at all.\n";

# ---- 6. the heuristic everyone writes first: "packages first"
sub pkgs_first { my @l = sort @_; return ((grep { /_pkg\.sv$/ } @l), (grep { !/_pkg\.sv$/ } @l)) }
print "\nthe 'packages first' heuristic:\n";
build("packages first, then the rest", pkgs_first(@FILES));

# ---- 7. now rename a package FILE so it sorts after the package that needs it.
# The package NAME inside is unchanged; only the filename moves in sort order.
print "\n--- rename chip_pkg.sv -> zz_chip_pkg.sv (same package inside) ---\n";
rename "rtl/core/chip_pkg.sv", "rtl/core/zz_chip_pkg.sv" or die "rename: $!";
my @renamed = map { $_ eq "rtl/core/chip_pkg.sv" ? "rtl/core/zz_chip_pkg.sv" : $_ } @FILES;

build("packages first, after rename", pkgs_first(@renamed));

# re-derive dependencies for the renamed set and re-sort topologically
my (%d2, %n2);
for my $f (@renamed) {
    open my $fh, "<", $f or die "$f: $!";
    while (my $l = <$fh>) {
        $d2{$f}{$1} = 1 if $l =~ /^\s*package\s+(\w+)\s*;/;
        $d2{$f}{$1} = 1 if $l =~ /^\s*interface\s+(\w+)\b/;
        $n2{$f}{$1} = 1 if $l =~ /^\s*import\s+(\w+)\s*::/;
    }
    close $fh;
}
my %p2;
for my $f (@renamed) { $p2{$_} = $f for keys %{ $d2{$f} // {} } }
my (%s2, @o2);
sub visit2 {
    my ($f) = @_;
    return if ($s2{$f} // "") ne "";
    $s2{$f} = "open";
    for my $name (sort keys %{ $n2{$f} // {} }) {
        my $dep = $p2{$name};
        visit2($dep) if defined $dep && $dep ne $f;
    }
    $s2{$f} = "done";
    push @o2, $f;
}
visit2($_) for @renamed;
build("topological, after rename", @o2);
print "  derived order now: ", join(" ", map { (split m{/}, $_)[-1] } @o2), "\n";

rename "rtl/core/zz_chip_pkg.sv", "rtl/core/chip_pkg.sv";

FILE                       DEFINES                NEEDS
rtl/core/alu.sv            -                      types_pkg
rtl/core/chip_pkg.sv       chip_pkg               -
rtl/core/counter.sv        -                      chip_pkg
rtl/core/types_pkg.sv      types_pkg              chip_pkg
tb/tb_counter.sv           -                      -

topological order:
  1. rtl/core/chip_pkg.sv
  2. rtl/core/types_pkg.sv
  3. rtl/core/alu.sv
  4. rtl/core/counter.sv
  5. tb/tb_counter.sv
cycles detected: none

hand each ordering to the compiler:
  topological (derived)          rc=0   compiles
  alphabetical by path           rc=2   rtl/core/alu.sv:9: syntax error
  reverse alphabetical           rc=2   rtl/core/types_pkg.sv:2: syntax error
  directory walk order           rc=2   rtl/core/alu.sv:9: syntax error
  packages last                  rc=6   rtl/core/alu.sv:9: syntax error

is alphabetical order reliable, or lucky here?
  alphabetical order violates 1 dependency(ies):
    rtl/core/alu.sv needs types_pkg from rtl/core/types_pkg.sv, which sorts AFTER it
  rename chip_pkg.sv to zz_chip_pkg.sv and alphabetical breaks;
  the topological order does not depend on the spelling at all.

the 'packages first' heuristic:
  packages first, then the rest  rc=0   compiles

--- rename chip_pkg.sv -> zz_chip_pkg.sv (same package inside) ---
  packages first, after rename   rc=2   rtl/core/types_pkg.sv:2: syntax error
  topological, after rename      rc=0   compiles
  derived order now: zz_chip_pkg.sv types_pkg.sv alu.sv counter.sv tb_counter.sv

The table at the top of that output is the whole input to the problem. chip_pkg.sv defines chip_pkg and needs nothing. types_pkg.sv defines types_pkg and needs chip_pkg — a package that depends on a package, which is what makes this a graph rather than two buckets. counter.sv and alu.sv define nothing and each need one package. The testbench needs nothing by import.

2. The Sort

The sort itself is a depth-first walk with three states per file:

sub visit {
    my ($f, @path) = @_;
    return if ($state{$f} // "") eq "done";                      # already placed
    if (($state{$f} // "") eq "open") { push @cycle, ...; return } # came back to it
    $state{$f} = "open";
    for my $name (sort keys %{ $needs{$f} // {} }) {
        my $dep = $provider{$name};
        next unless defined $dep && $dep ne $f;
        visit($dep, @path, $f);
    }
    $state{$f} = "done";
    push @order, $f;                                             # AFTER its deps
}

Four details carry the whole thing:

push @order, $f happens after the loop. A file is appended only once everything it needs has been appended, which is what makes the output an order rather than a list. Chapter 10.9's recursion, with the work done on the way back up.

Three states, not two. done prevents re-emitting a file reached by two paths; open is what detects a cycle. A two-state version — seen or not — cannot tell "already finished" from "currently being visited", and those are the two cases that matter.

sort keys on the needs. Chapter 6.6 measured that hash order changes between runs; without the sort, a file with two dependencies could emit them in either order, and two runs of the generator would produce two different filelists. Chapter 17.8's requirement, applied inside the sort.

defined $dep is load-bearing. An import of a package no file provides — a package from a precompiled library, or a typo — leaves $provider{$name} undefined. Skipping it keeps the sort working on the part of the graph it does know, instead of dying.

3. Five Orderings, One Compiles

The measurement's middle block is the point of the chapter:

Four of five fail, and the violation report says exactly why alphabetical does: alu.sv needs types_pkg from types_pkg.sv, which sorts AFTER it. The letter a comes before t, and the design does not care about the alphabet.

Notice also what the failures look like. alu.sv:9: syntax error — line 9 of alu.sv is the import, and the message is the same syntax error Chapter 19.1 measured, naming neither the package nor the ordering. Reverse alphabetical fails at a different file, so even the location of the error moves with the ordering, which makes it a poor clue about the cause.

4. The Heuristic That Passes Today

The last block is the one to take away.

"Packages first, then everything else" compiles. rc=0. It is the heuristic almost every hand-written generator uses, it takes one line of grep, and on this tree it is correct.

Then rename chip_pkg.sv to zz_chip_pkg.sv. The package inside is still called chip_pkg; no source line changes; no logic changes. And:

packages first, after rename   rc=2   rtl/core/types_pkg.sv:2: syntax error
topological, after rename      rc=0   compiles

The heuristic breaks on a rename. It worked before because the two package files happened to sort in dependency order — chip before types — and that was luck, not design. The topological sort is unaffected, because it never looked at the filenames: its re-derived order is zz_chip_pkg.sv types_pkg.sv alu.sv counter.sv tb_counter.sv.

I should be straight about something here. The scripts in Chapters 19.1 to 19.4 use that same pkgs_first heuristic, and they compile. They compile for exactly the reason just measured — the package filenames in this tree sort in dependency order — and this chapter is where that debt is paid. Using it there was fine: those chapters were measuring something else and needed an order that worked. Shipping it in a generator is not fine, and the difference is that a generator has to keep working after a rename nobody tells you about.

5. Cycles, And What A Cycle Means

The measurement reports cycles: none, and the cycle check still earns its place for two reasons.

Without it the sort does not fail, it hangs. The visit is recursive, so a cycle is an infinite descent. Chapter 17.1 made the same point about walking up a tree to find a project root: a loop needs a termination check, and the check has to exist before you need it.

A cycle is a real finding about the design. Two packages that import each other is not a filelist problem — no ordering of a cyclic graph compiles, so there is nothing a generator can do with it except report it clearly:

cycle: rtl/core/a_pkg.sv -> rtl/core/b_pkg.sv -> rtl/core/a_pkg.sv

That message names the files and the direction, which is what somebody needs to break the cycle — usually by moving the shared types into a third package. Chapter 19.3's module-name clash had the same character: the generator's job is to state the problem precisely and stop, not to guess.

One honest limit, in the spirit of Chapter 18.11. This whole chapter is patterns over source, so it sees package, interface and import only where they are the first thing on a line. It will miss an import inside a generate block indented behind other code, and it will count one inside a block comment. For a filelist generator that trade is right — the result is checked immediately by the compiler, which is the authority — but it is a scan, not a parser, and a design that defeats it needs the tool's own dependency output instead.

6. What To Remember

• Order is the one thing in a filelist you cannot read off the filesystem — it comes from what the files say about each other.
• Two questions per file: what does it define (package, interface), and what does it need (import).
• A package can depend on a package — that is what makes it a graph, not two buckets.
• Build a provider map first, turning a dependency on a name into a dependency on a file.
• Depth-first visit, appending a file only after its dependencies — recursion with the work on the way back up (10.9).
• Three states, not two. done stops re-emitting; open is what detects a cycle.
• sort keys on the needs, or two runs give two filelists (6.6, 17.8).
• defined $dep keeps an unprovided import from killing the sort — a precompiled library package has no file.
• Measured: four of five naive orderings fail. Alphabetical, reverse, walk order and packages-last all fail.
• Alphabetical violated one dependency: alu.sv needs types_pkg, which sorts after it.
• A wrong order gives syntax error, not "not found" — import unknown::*; does not parse, so the error lands on the importing line and names nothing useful.
• The error's location moves with the ordering, so it is a poor clue about the cause.
• Measured: "packages first" compiles — then fails after renaming chip_pkg.sv to zz_chip_pkg.sv, with no logic change at all.
• It worked by luck: the package filenames happened to sort in dependency order.
• The topological order is spelling-blind and was unaffected by the rename.
• The person who renames the file is not the person who gets the error, and the message has no path back to a rename.
• Keep the cycle check: without it a cycle hangs the generator rather than failing it.
• A cycle is a design finding — report the files and the direction, and stop.
• This is a scan, not a parser (18.11) — right for a generator the compiler immediately checks, wrong as a source of truth about a design.

Chapter 19.6 takes the same source tree and asks it to produce more than one filelist. A design has configurations — RTL or gate-level, assertions on or off — and the generator should derive all of them from one description rather than leaving several hand-maintained lists to drift apart.