[WIP] Implement CircuitGraph and IRLookup to firrtl.analyses (#1603)

* WIP Commit

* Add EdgeDataDiGraph with views to amortize graph construction

* WIP, got basic structure, need tests to pipeclean

* First tests pass. Need more.

* Tests pass, more need to be written

* More tests pass! Things should work, except for memories

* Added clearPrev to fix digraph uses where caching prev breaks

* Removed old Component. Documented IRLookup

* Added comments. Make prev arg to getEdges

* WIP: Refactoring for CircuitGraph

* Refactored into CircuitGraph. Can do topological module analysis

* Removed old versions

* Added support for memories

* Added cached test

* More stufffff

* Added implicit caching of connectivity

* Added tests for IRLookup, and others

* Many major changes.

Replaced CircuitGraph as ConnectionGraph
Added CircuitGraph to be top-level user-facing object
ConnectionGraph now automatically shortcuts getEdges
ConnectionGraph overwrites BFS as PriorityBFS
Added leafModule to Target
Added lookup by kind to IRLookup
Added more tests

* Reordered stuff in ConnectionGraph

* Made path work with deep hierarchies. Added PML for IllegalClockCrossings

* Made pathsInDAG work with current shortcut semantics

* Bugfix: check pathless targets when shortcutting paths

* Added documentation/licenses

* Removed UnnamedToken and related functionality

* Added documentation of ConnectionGraph

* Added back topo, needed for correct solving of intermediate modules

* Bugfix. Cache intermediate clockSources from same BFS with same root, but not BFS with different root

* Added literal/invalid clock source, and unknown top for getclocksource

* Bugfix for clocks in bundles

* Add CompleteTargetSerializer and test

* remove ClockFinder, be able to compile.

* test is able to compile, but need to fix.

* public and abstract DiGraph, remove DiGraphLike.

* revert some DiGraph code, ConnectionGraphSpec passed.

* CircuitGraphSpec passed.

* minimize diff between master

* codes clean up

* override linearize and revert DiGraph

* keep DiGraph unchanged.

* make ci happy again.

* codes clean up.

* bug fix for rebase

* remove wir

* make scaladoc happy again.

* update for review.

* add some documentation.

* remove tag

* wip IRLookup

* code clean up and add some doucmentations.

* IRLookup cache with ModuleTarget guarded.

* make unidoc and 2.13 happy

Co-authored-by: Adam Izraelevitz <azidar@gmail.com>
Co-authored-by: Albert Magyar <albert.magyar@gmail.com>
Co-authored-by: Jack Koenig <koenig@sifive.com>

1 files changed, 107 insertions, 0 deletions

diff --git a/src/test/scala/firrtlTests/analyses/ConnectionGraphSpec.scala b/src/test/scala/firrtlTests/analyses/ConnectionGraphSpec.scala
new file mode 100644
index 00000000..06f59a3c
--- /dev/null
+++ b/src/test/scala/firrtlTests/analyses/ConnectionGraphSpec.scala
@@ -0,0 +1,107 @@
+// See LICENSE for license details.
+
+package firrtlTests.analyses
+
+import firrtl.{ChirrtlForm, CircuitState, FileUtils, IRToWorkingIR, UnknownForm}
+import firrtl.analyses.{CircuitGraph, ConnectionGraph}
+import firrtl.annotations.ModuleTarget
+import firrtl.options.Dependency
+import firrtl.passes.ExpandWhensAndCheck
+import firrtl.stage.{Forms, TransformManager}
+import firrtl.testutils.FirrtlFlatSpec
+
+class ConnectionGraphSpec extends FirrtlFlatSpec {
+
+  "ConnectionGraph" should "build connection graph for rocket-chip" in {
+    ConnectionGraph(
+      new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform(
+        CircuitState(parse(FileUtils.getTextResource("/regress/RocketCore.fir")), UnknownForm)
+      ).circuit
+    )
+  }
+
+  val input =
+    """circuit Test:
+      |  module Test :
+      |    input in: UInt<8>
+      |    input clk: Clock
+      |    input reset: UInt<1>
+      |    output out: {a: UInt<8>, b: UInt<8>[2]}
+      |    out is invalid
+      |    reg r: UInt<8>, clk with:
+      |      (reset => (reset, UInt(0)))
+      |    r <= in
+      |    node x = r
+      |    wire y: UInt<8>
+      |    y <= x
+      |    out.b[0] <= and(y, asUInt(SInt(-1)))
+      |    inst child of Child
+      |    child.in <= in
+      |    out.a <= child.out
+      |  module Child:
+      |    input in: UInt<8>
+      |    output out: UInt<8>
+      |    out <= in
+      |""".stripMargin
+
+  val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform(
+    CircuitState(parse(input), UnknownForm)
+  ).circuit
+
+  "ConnectionGraph" should "work with pathsInDAG" in {
+    val Test = ModuleTarget("Test", "Test")
+    val irGraph = ConnectionGraph(circuit)
+
+    val paths = irGraph.pathsInDAG(Test.ref("in"))
+    paths(Test.ref("out").field("b").index(0)) shouldBe Seq(
+      Seq(
+        Test.ref("in"),
+        Test.ref("r"),
+        Test.ref("x"),
+        Test.ref("y"),
+        Test.ref("@and#0"),
+        Test.ref("out").field("b").index(0)
+      )
+    )
+    paths(Test.ref("out").field("a")) shouldBe Seq(
+      Seq(
+        Test.ref("in"),
+        Test.ref("child").field("in"),
+        Test.instOf("child", "Child").ref("in"),
+        Test.instOf("child", "Child").ref("out"),
+        Test.ref("child").field("out"),
+        Test.ref("out").field("a")
+      )
+    )
+
+  }
+
+  "ConnectionGraph" should "work with path" in {
+    val Test = ModuleTarget("Test", "Test")
+    val irGraph = ConnectionGraph(circuit)
+
+    irGraph.path(Test.ref("in"), Test.ref("out").field("b").index(0)) shouldBe Seq(
+      Test.ref("in"),
+      Test.ref("r"),
+      Test.ref("x"),
+      Test.ref("y"),
+      Test.ref("@and#0"),
+      Test.ref("out").field("b").index(0)
+    )
+
+    irGraph.path(Test.ref("in"), Test.ref("out").field("a")) shouldBe Seq(
+      Test.ref("in"),
+      Test.ref("child").field("in"),
+      Test.instOf("child", "Child").ref("in"),
+      Test.instOf("child", "Child").ref("out"),
+      Test.ref("child").field("out"),
+      Test.ref("out").field("a")
+    )
+
+    irGraph.path(Test.ref("@invalid#0"), Test.ref("out").field("b").index(1)) shouldBe Seq(
+      Test.ref("@invalid#0"),
+      Test.ref("out").field("b").index(1)
+    )
+  }
+
+}