Walking the Hierarchy

Part II · Module 19 · Chapter 19.1 · Walking the Hierarchy

Module 18 taught the query commands. This module is about the queries themselves — the handful you end up writing again on every project, and the reason a senior engineer answers a structural question in thirty seconds while someone else opens a viewer.

"How many sequential cells are in the memory block?" is not a browsing problem on a two-million-instance netlist. It is one command.

1. The hierarchy is already in the name

The realisation that makes this chapter easy: an instance name is a path.

u_core/u_ctrl

That is u_ctrl, inside u_core. The separator is structural, so everything you want to know about position — depth, parent, children — is derivable with ordinary Tcl.

proc depth {name} { return [llength [split $name /]] }
proc parent {name} {
    set p [file dirname $name]
    return [expr {$p eq "." ? "" : $p}]
}

  depth 1  u_core               parent ''
  depth 2  u_core/u_ctrl        parent 'u_core'
  depth 2  u_core/u_alu         parent 'u_core'
  depth 2  u_core/u_pipe_reg    parent 'u_core'
  depth 1  u_mem                parent ''
  depth 2  u_mem/u_bank0        parent 'u_mem'
  depth 2  u_mem/u_bank1        parent 'u_mem'
  depth 1  u_io                 parent ''
  depth 2  u_io/u_sync          parent 'u_io'

Two procedures, four lines, no tool commands. split on the separator gives depth; file dirname and file tail give parent and leaf — the path commands from Chapter 12.10, used on something that is not a filename but has the same shape.

2. What is inside each block

The single most useful structural query, and the shape most of this module's examples take:

foreach_in_collection blk [get_cells *] {
    set inside [get_cells -hierarchical "$blk/*"]
    puts [format "  %-8s %d instance(s): %s" $blk [sizeof_collection $inside] [collection_to_list $inside]]
}

  u_core   3 instance(s): u_core/u_ctrl u_core/u_alu u_core/u_pipe_reg
  u_mem    2 instance(s): u_mem/u_bank0 u_mem/u_bank1
  u_io     1 instance(s): u_io/u_sync

The outer loop walks the top-level blocks; the inner query builds a pattern from each block's name. Because the pattern is constructed, the loop works for three blocks or three hundred.

Note "$blk/*" is quoted, not braced — $blk must be substituted. That is the Chapter 2.9 decision rule, and getting it backwards here gives you a literal pattern that matches nothing, which Chapter 18.8 says will fail silently.

3. An indented tree

Sometimes you do want to see the shape. You do not need a viewer:

foreach c [lsort [collection_to_list [get_cells -hierarchical *]]] {
    set d [expr {[llength [split $c /]] - 1}]
    puts "  [string repeat {    } $d][file tail $c]"
}

  u_core
      u_alu
      u_ctrl
      u_pipe_reg
  u_io
      u_sync
  u_mem
      u_bank0
      u_bank1

Three lines of ordinary Tcl. lsort puts each parent immediately before its children because the path prefix sorts that way; the indent is the depth; file tail prints the leaf.

4. Counting, which is usually the real question

Structural questions are mostly counting questions, and counting is what makes a query better than a viewer:

set all  [get_cells -hierarchical *]
set seq  [filter_collection $all "is_sequential == true"]
puts "  [sizeof_collection $all] instances, [sizeof_collection $seq] sequential"

Per block, which is how such a report is actually wanted:

foreach_in_collection blk [get_cells *] {
    set inside [get_cells -hierarchical "$blk/*"]
    set seq    [filter_collection $inside "is_sequential == true"]
    puts [format "  %-8s %3d cells  %3d sequential" \
        $blk [sizeof_collection $inside] [sizeof_collection $seq]]
}

That is the shape from Chapter 18.5 §6, and it is worth noticing how little of it is EDA. Two tool commands supply the data; the loop, the formatting and the arithmetic are Part I.

5. Depth, and what it tells you

Grouping by depth answers "how deeply nested is this design", which matters because deep hierarchy affects runtime and makes names unwieldy:

array set bydepth {}
foreach_in_collection c [get_cells -hierarchical *] {
    incr bydepth([llength [split $c /]])
}
foreach d [lsort -integer [array names bydepth]] {
    puts "  depth $d: $bydepth($d) instance(s)"
}

An array as a tally, incr creating the key on first use, lsort -integer on the keys. Again: the tool supplies the names, Part I does the work.

6. Finding where something lives

A specific question you will be asked often: where in the hierarchy is this?

proc find_instance {pattern} {
    set hits [get_cells -hierarchical $pattern]
    if {[sizeof_collection $hits] == 0} {
        error "nothing matched '$pattern'" {} [list DESIGN NOMATCH $pattern]
    }
    foreach_in_collection c $hits {
        puts [format "  %-22s depth %d  in %s" $c [depth $c] [parent $c]]
    }
    return $hits
}

The guard matters as much as the query. Without it, a mistyped pattern prints nothing and looks like "this design has no such instance" rather than "you spelled it wrong" — the distinction Chapter 18.8 is entirely about.

7. Scale

Everything above runs on nine cells. The reason it matters is what happens at two million.

A viewer requires you to know where to look. A query does not — get_cells -hierarchical *fifo* searches the whole tree in one command, and the answer is a number you can compare against last week's.

Two cautions at that scale, both from Module 18:

• Do not convert large collections to lists unless you need the names. collection_to_list on two million instances materialises two million strings, which is the cost collections exist to avoid — Chapter 18.2 §6.
• Filter in the tool, not in Tcl. filter_collection is evaluated by the tool; a foreach_in_collection with an if inside is evaluated object by object in Tcl — Chapter 18.7 §3.

Both are invisible on nine cells and decisive on two million.

8. Exercises

Exercise 1. What makes depth and parent derivable without a traversal command?

Exercise 2. Write depth and parent using ordinary Tcl.

Exercise 3. In the per-block loop, why is the inner pattern "$blk/*" quoted rather than braced?

Exercise 4. Why does lsort make the indented tree nest correctly, and when would it not?

Exercise 5. What does incr bydepth($d) rely on when the key does not yet exist?

Exercise 6. Why guard find_instance with a size check?

Exercise 7. Name two things to avoid when the same query runs on two million instances.