Quadratic naming with recursive functions

[jackkoenig]

When using an intermediate Wire (or Reg, any Data) in a recursive function, the new naming behavior results in a quadratic naming blowup:

def func(bools: Seq[Bool]): Bool = {
  if (bools.isEmpty) true.B
  else {
    val w = Wire(Bool())
    w := bools.head && func(bools.tail)
    w
  }
}
// Call it in a Module
val x = func(io.in)

This gives:

    wire x : UInt<1>
    wire x_x_w : UInt<1>
    wire x_x_x_x_w_w : UInt<1>
    wire x_x_x_x_w_x_x_x_x_w_w_w : UInt<1>
    node _x_x_x_x_w_x_x_x_x_w_w_x_x_x_x_w_x_x_x_x_w_w_w_T = and(io.in[3], UInt<1>("h1"))
    x_x_x_x_w_x_x_x_x_w_w_w <= _x_x_x_x_w_x_x_x_x_w_w_x_x_x_x_w_x_x_x_x_w_w_w_T
    node _x_x_x_x_w_x_x_x_x_w_w_T = and(io.in[2], x_x_x_x_w_x_x_x_x_w_w_w)
    x_x_x_x_w_w <= _x_x_x_x_w_x_x_x_x_w_w_T
    node _x_x_x_x_w_T = and(io.in[1], x_x_x_x_w_w)
    x_x_w <= _x_x_x_x_w_T
    node _x_x_T = and(io.in[0], x_x_w)
    x <= _x_x_T

Executable example: https://scastie.scala-lang.org/O0xhmu4eRgqdXmUb2CfqbA

While this is very funny, it's also an important bug to fix. Internally I'm seeing names well over 2000 characters long and since the Verilog spec allows tools to only support names up to 1024 characters, we're already hitting problems in various tools.

Type of issue: bug report

Impact: no functional change

Development Phase: request

[aswaterman]

lol.

What's the desired behavior? It shouldn't grow linearly, either, or the same sort of issues will crop up eventually, especially with longer base names. If you rewrite this example iteratively (https://scastie.scala-lang.org/b2r2IB3cQFWALeO1SpFFKQ) you get logarithmic growth in the form of a postfixed integer, which seems desirable.

Yet, we presumably do want multiple non-recursive function calls to build up these longish names. Maybe we could heuristically filter out the recursive (and mutually recursive) cases by not adding a prefix that has already been added before. Maybe it is as simple as building up a list of prefixes that have been used (("x", "w") in this case) and not adding a prefix that has already been used.

[jackkoenig]

For fixing just the quadratic issue, I think there's a straightforward solution. Basically this occurs because when doing a connection, eg. w := bools.head && func(bools.tail), it's not the "local" name w that is used as a prefix, rather it's the full already prefixed name (eg. x_x_w) which gets combined with the prefix for the current place in the call stack ("x" :: "x" :: Nil) if that makes sense. I think the fix is just to make the prefix from the connection just be "w".

As for the linear growth issue, obviously we don't want that either, but I am treating it as a separate issue. It's admittedly not the best user experience but I was just thinking about adding a stripPrefix or popPrefix call to deal with the linear growth. I'm not sure how to distinguish otherwise unless we also want the plugin to try to identify recursion. That's probably doable, but the issue will still crop up in mutual recursion.

[jackkoenig]

We could try to filter out prefixes that we've already seen so that's an option, but that would likely affect places where it may be desirable to repeat a prefix once or twice based on a particular call stack (in non-recursive places).

[aswaterman]

Or, more simply, truncate the prefix to (N - suffix-length) chars, where N is the longest name we want to support. You're right, separate issue, though.