A faster way to sort HDL files in HDLRegression

HDLRegression has for a long time relied on a bubble sort-like routine to arrange HDL files in compile order. This approach simply swapped files around until it found a sequence that satisfied all dependencies. We are continuously working on improvements of this tool and some of these improvements are to accelerate compile order and more reliably detect any dependency loops.

The old approach

Originally, the code would scan the list of files multiple times, trying to “bubble” each file into its correct position based on its dependencies. If file A depends on file B, A must come after B. The sorting loop would swap files until the order looked right. The bubble sort algorithm is simple, but has some downsides:

1. It takes lot of passes to correct the order if there are many dependencies.
2. It can struggle to detect cycles where two files depend on each other in some way.

Why we need a better method

For large designs the bubble-sort-like approach can became slow; each pass checked dependencies between pairs of files, leading to a worst-case time complexity similar to O(n2). Another challenge is the detection of circular dependencies—situations where files end up depending on each other, blocking a correct compile order.

Kahn’s Algorithm

There are several sorting algorithms that can be used for this problem, and one of these is the Kahn’s algorithm, which is a classic method for topological sorting of Directed Acyclic Graphs (DAGs). In the context of HDLRegression, we treat each HDL file as a node in a graph. If file A depends on file B, we draw a directed edge from B to A, meaning “B must come before A.”

Overview of Kahn’s Algorithm

A somewhat simplified description of how the algorithm is used in HDLRegression:

1. Count incoming edges (indegree) - each file starts with a count of how many other files it depends on.
2. Identify files with zero indegree - these files have no dependencies, so we can compile them first.
3. Remove processed files from the graph - once a file is taken out, decrement the indegree of files that depend on it. If any of these drop to zero indegree, they become the next candidates for compilation.
4. Detect cycles - if at some point no file has zero indegree, but there are still files left unprocessed, it means there’s a cycle in the graph in we can have issues with how to determine the correct compile order.

The figure below illustrates a small DAG example for Kahn's algorithm with three nodes and their edges indicating dependency directions. In this example item B has to come before item A, and item A has to come before item C. The topologic sorting is then B, A, C.

Adaptations in HDLRegression

While Kahn’s algorithm is straightforward, HDLRegression adds two small adjustments to prevent false circular errors and make the algorithm more efficient for typical HDL projects, where multiple design units can reside in the same file:

1. As we are working with HDL files, we have the possibility of same-file dependencies: If two modules are in the same physical file, we don’t create a dependency.
2. Another thing that has to be handled are other libraries: If a dependency points to a file in another library, we skip it in the current library’s graph because each library is sorted on its own.

The figure below shows a possible scenario for an ignore same-file dependency. Here HDLRegression will create 3 VHDL module objects, an Entity, an Architecture and a Package, where all files are written in the same file. Normally the package, if used in the architecture, would have to be placed before the architecture in the topologic sorting, and the entity after the architecture. Because all of these module objects belong to the same file, the order does not matter for the compile order.

Switching from bubble-sort to Kahn’s algorithm has two major benefits:

1. Kahn’s runs in O(V + E) time, where V is the number of files and E is the number of dependency edges. This is significantly faster than the O(n2) approach for large n.
2. Cycle detection is now built-in, meaning if a cycle exists, we immediately know rather than getting stuck in endless swaps or receiving only partial error messages.

Conclusion

By implementing Kahn’s algorithm, HDLRegression can now handle hundreds or even thousands of HDL files with complex dependency graphs even faster. The algorithm accelerates compilation order resolution and provides clear error messages when genuine dependency loops occur.

Read more about HDLRegression here and download from Github.

Inventas #FPGA #ASIC #HDLRegression #UVVM #Embedded #Methodology