From f22652a330afe1daa77be2aadb525d65ab05e9fe Mon Sep 17 00:00:00 2001 From: Jiuyang Liu Date: Sat, 1 Aug 2020 00:25:13 +0800 Subject: [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 Co-authored-by: Albert Magyar Co-authored-by: Jack Koenig --- .../firrtlTests/analyses/CircuitGraphSpec.scala | 50 ++++ .../firrtlTests/analyses/ConnectionGraphSpec.scala | 107 ++++++++ .../scala/firrtlTests/analyses/IRLookupSpec.scala | 296 +++++++++++++++++++++ .../transforms/GroupComponentsSpec.scala | 2 + 4 files changed, 455 insertions(+) create mode 100644 src/test/scala/firrtlTests/analyses/CircuitGraphSpec.scala create mode 100644 src/test/scala/firrtlTests/analyses/ConnectionGraphSpec.scala create mode 100644 src/test/scala/firrtlTests/analyses/IRLookupSpec.scala (limited to 'src/test') diff --git a/src/test/scala/firrtlTests/analyses/CircuitGraphSpec.scala b/src/test/scala/firrtlTests/analyses/CircuitGraphSpec.scala new file mode 100644 index 00000000..79922fa9 --- /dev/null +++ b/src/test/scala/firrtlTests/analyses/CircuitGraphSpec.scala @@ -0,0 +1,50 @@ +// See LICENSE for license details. + +package firrtlTests.analyses + +import firrtl.analyses.CircuitGraph +import firrtl.annotations.CircuitTarget +import firrtl.options.Dependency +import firrtl.passes.ExpandWhensAndCheck +import firrtl.stage.{Forms, TransformManager} +import firrtl.testutils.FirrtlFlatSpec +import firrtl.{ChirrtlForm, CircuitState, FileUtils, UnknownForm} + +class CircuitGraphSpec extends FirrtlFlatSpec { + "CircuitGraph" should "find paths with deep hierarchy quickly" in { + def mkChild(n: Int): String = + s""" module Child${n} : + | input in: UInt<8> + | output out: UInt<8> + | inst c1 of Child${n+1} + | inst c2 of Child${n+1} + | c1.in <= in + | c2.in <= c1.out + | out <= c2.out + """.stripMargin + def mkLeaf(n: Int): String = + s""" module Child${n} : + | input in: UInt<8> + | output out: UInt<8> + | wire middle: UInt<8> + | middle <= in + | out <= middle + """.stripMargin + (2 until 23 by 2).foreach { n => + val input = new StringBuilder() + input ++= + """circuit Child0: + |""".stripMargin + (0 until n).foreach { i => input ++= mkChild(i); input ++= "\n" } + input ++= mkLeaf(n) + val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform( + CircuitState(parse(input.toString()), UnknownForm) + ).circuit + val circuitGraph = CircuitGraph(circuit) + val C = CircuitTarget("Child0") + val Child0 = C.module("Child0") + circuitGraph.connectionPath(Child0.ref("in"), Child0.ref("out")) + } + } + +} 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) + ) + } + +} diff --git a/src/test/scala/firrtlTests/analyses/IRLookupSpec.scala b/src/test/scala/firrtlTests/analyses/IRLookupSpec.scala new file mode 100644 index 00000000..50ee75ac --- /dev/null +++ b/src/test/scala/firrtlTests/analyses/IRLookupSpec.scala @@ -0,0 +1,296 @@ +package firrtlTests.analyses + +import firrtl.PrimOps.AsUInt +import firrtl.analyses.IRLookup +import firrtl.annotations.{CircuitTarget, ModuleTarget, ReferenceTarget} +import firrtl._ +import firrtl.ir._ +import firrtl.options.Dependency +import firrtl.passes.ExpandWhensAndCheck +import firrtl.stage.{Forms, TransformManager} +import firrtl.testutils.FirrtlFlatSpec + + +class IRLookupSpec extends FirrtlFlatSpec { + + "IRLookup" should "return declarations" in { + 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]} + | input ana1: Analog<8> + | output ana2: Analog<8> + | out is invalid + | reg r: UInt<8>, clk with: + | (reset => (reset, UInt(0))) + | node x = r + | wire y: UInt<8> + | y <= x + | out.b[0] <= and(y, asUInt(SInt(-1))) + | attach(ana1, ana2) + | inst child of Child + | out.a <= child.out + | module Child: + | output out: UInt<8> + | out <= UInt(1) + |""".stripMargin + + val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform( + CircuitState(parse(input), UnknownForm) + ).circuit + val irLookup = IRLookup(circuit) + val Test = ModuleTarget("Test", "Test") + val uint8 = UIntType(IntWidth(8)) + + irLookup.declaration(Test.ref("in")) shouldBe Port(NoInfo, "in", Input, uint8) + irLookup.declaration(Test.ref("clk")) shouldBe Port(NoInfo, "clk", Input, ClockType) + irLookup.declaration(Test.ref("reset")) shouldBe Port(NoInfo, "reset", Input, UIntType(IntWidth(1))) + + val out = Port(NoInfo, "out", Output, + BundleType(Seq(Field("a", Default, uint8), Field("b", Default, VectorType(uint8, 2)))) + ) + irLookup.declaration(Test.ref("out")) shouldBe out + irLookup.declaration(Test.ref("out").field("a")) shouldBe out + irLookup.declaration(Test.ref("out").field("b").index(0)) shouldBe out + irLookup.declaration(Test.ref("out").field("b").index(1)) shouldBe out + + irLookup.declaration(Test.ref("ana1")) shouldBe Port(NoInfo, "ana1", Input, AnalogType(IntWidth(8))) + irLookup.declaration(Test.ref("ana2")) shouldBe Port(NoInfo, "ana2", Output, AnalogType(IntWidth(8))) + + val clk = WRef("clk", ClockType, PortKind, SourceFlow) + val reset = WRef("reset", UIntType(IntWidth(1)), PortKind, SourceFlow) + val init = UIntLiteral(0) + val reg = DefRegister(NoInfo, "r", uint8, clk, reset, init) + irLookup.declaration(Test.ref("r")) shouldBe reg + irLookup.declaration(Test.ref("r").clock) shouldBe reg + irLookup.declaration(Test.ref("r").reset) shouldBe reg + irLookup.declaration(Test.ref("r").init) shouldBe reg + irLookup.kindFinder(Test, RegKind) shouldBe Seq(Test.ref("r")) + irLookup.declaration(Test.ref("x")) shouldBe DefNode(NoInfo, "x", WRef("r", uint8, RegKind, SourceFlow)) + irLookup.declaration(Test.ref("y")) shouldBe DefWire(NoInfo, "y", uint8) + + irLookup.declaration(Test.ref("@and#0")) shouldBe + DoPrim(PrimOps.And, + Seq(WRef("y", uint8, WireKind, SourceFlow), DoPrim(AsUInt, Seq(SIntLiteral(-1)), Nil, UIntType(IntWidth(1)))), + Nil, + uint8 + ) + + val inst = WDefInstance(NoInfo, "child", "Child", BundleType(Seq(Field("out", Default, uint8)))) + irLookup.declaration(Test.ref("child")) shouldBe inst + irLookup.declaration(Test.ref("child").field("out")) shouldBe inst + irLookup.declaration(Test.instOf("child", "Child").ref("out")) shouldBe Port(NoInfo, "out", Output, uint8) + + intercept[IllegalArgumentException]{ irLookup.declaration(Test.instOf("child", "Child").ref("missing")) } + intercept[IllegalArgumentException]{ irLookup.declaration(Test.instOf("child", "Missing").ref("out")) } + intercept[IllegalArgumentException]{ irLookup.declaration(Test.instOf("missing", "Child").ref("out")) } + intercept[IllegalArgumentException]{ irLookup.declaration(Test.ref("missing")) } + intercept[IllegalArgumentException]{ irLookup.declaration(Test.ref("out").field("c")) } + intercept[IllegalArgumentException]{ irLookup.declaration(Test.instOf("child", "Child").ref("out").field("missing")) } + } + + "IRLookup" should "return mem declarations" in { + def commonFields: Seq[String] = Seq("clk", "en", "addr") + def readerTargets(rt: ReferenceTarget): Seq[ReferenceTarget] = { + (commonFields ++ Seq("data")).map(rt.field) + } + def writerTargets(rt: ReferenceTarget): Seq[ReferenceTarget] = { + (commonFields ++ Seq("data", "mask")).map(rt.field) + } + def readwriterTargets(rt: ReferenceTarget): Seq[ReferenceTarget] = { + (commonFields ++ Seq("wdata", "wmask", "wmode", "rdata")).map(rt.field) + } + val input = + s"""circuit Test: + | module Test : + | input in : UInt<8> + | input clk: Clock[3] + | input dataClk: Clock + | input mode: UInt<1> + | output out : UInt<8>[2] + | mem m: + | data-type => UInt<8> + | reader => r + | writer => w + | readwriter => rw + | depth => 2 + | write-latency => 1 + | read-latency => 0 + | + | reg addr: UInt<1>, dataClk + | reg en: UInt<1>, dataClk + | reg indata: UInt<8>, dataClk + | + | m.r.clk <= clk[0] + | m.r.en <= en + | m.r.addr <= addr + | out[0] <= m.r.data + | + | m.w.clk <= clk[1] + | m.w.en <= en + | m.w.addr <= addr + | m.w.data <= indata + | m.w.mask <= en + | + | m.rw.clk <= clk[2] + | m.rw.en <= en + | m.rw.addr <= addr + | m.rw.wdata <= indata + | m.rw.wmask <= en + | m.rw.wmode <= en + | out[1] <= m.rw.rdata + |""".stripMargin + + val C = CircuitTarget("Test") + val MemTest = C.module("Test") + val Mem = MemTest.ref("m") + val Reader = Mem.field("r") + val Writer = Mem.field("w") + val Readwriter = Mem.field("rw") + val allSignals = readerTargets(Reader) ++ writerTargets(Writer) ++ readwriterTargets(Readwriter) + + val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform( + CircuitState(parse(input), UnknownForm) + ).circuit + val irLookup = IRLookup(circuit) + val uint8 = UIntType(IntWidth(8)) + val mem = DefMemory(NoInfo, "m", uint8, 2, 1, 0, Seq("r"), Seq("w"), Seq("rw")) + allSignals.foreach { at => + irLookup.declaration(at) shouldBe mem + } + } + + "IRLookup" should "return expressions, types, kinds, and flows" in { + 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]} + | input ana1: Analog<8> + | output ana2: Analog<8> + | out is invalid + | reg r: UInt<8>, clk with: + | (reset => (reset, UInt(0))) + | node x = r + | wire y: UInt<8> + | y <= x + | out.b[0] <= and(y, asUInt(SInt(-1))) + | attach(ana1, ana2) + | inst child of Child + | out.a <= child.out + | module Child: + | output out: UInt<8> + | out <= UInt(1) + |""".stripMargin + + val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform( + CircuitState(parse(input), UnknownForm) + ).circuit + val irLookup = IRLookup(circuit) + val Test = ModuleTarget("Test", "Test") + val uint8 = UIntType(IntWidth(8)) + val uint1 = UIntType(IntWidth(1)) + + def check(rt: ReferenceTarget, e: Expression): Unit = { + irLookup.expr(rt) shouldBe e + irLookup.tpe(rt) shouldBe e.tpe + irLookup.kind(rt) shouldBe Utils.kind(e) + irLookup.flow(rt) shouldBe Utils.flow(e) + } + + check(Test.ref("in"), WRef("in", uint8, PortKind, SourceFlow)) + check(Test.ref("clk"), WRef("clk", ClockType, PortKind, SourceFlow)) + check(Test.ref("reset"), WRef("reset", uint1, PortKind, SourceFlow)) + + val out = Test.ref("out") + val outExpr = + WRef("out", + BundleType(Seq(Field("a", Default, uint8), Field("b", Default, VectorType(uint8, 2)))), + PortKind, + SinkFlow + ) + check(out, outExpr) + check(out.field("a"), WSubField(outExpr, "a", uint8, SinkFlow)) + val outB = out.field("b") + val outBExpr = WSubField(outExpr, "b", VectorType(uint8, 2), SinkFlow) + check(outB, outBExpr) + check(outB.index(0), WSubIndex(outBExpr, 0, uint8, SinkFlow)) + check(outB.index(1), WSubIndex(outBExpr, 1, uint8, SinkFlow)) + + check(Test.ref("ana1"), WRef("ana1", AnalogType(IntWidth(8)), PortKind, SourceFlow)) + check(Test.ref("ana2"), WRef("ana2", AnalogType(IntWidth(8)), PortKind, SinkFlow)) + + val clk = WRef("clk", ClockType, PortKind, SourceFlow) + val reset = WRef("reset", UIntType(IntWidth(1)), PortKind, SourceFlow) + val init = UIntLiteral(0) + check(Test.ref("r"), WRef("r", uint8, RegKind, DuplexFlow)) + check(Test.ref("r").clock, clk) + check(Test.ref("r").reset, reset) + check(Test.ref("r").init, init) + + check(Test.ref("x"), WRef("x", uint8, ExpKind, SourceFlow)) + + check(Test.ref("y"), WRef("y", uint8, WireKind, DuplexFlow)) + + check(Test.ref("@and#0"), + DoPrim(PrimOps.And, + Seq(WRef("y", uint8, WireKind, SourceFlow), DoPrim(AsUInt, Seq(SIntLiteral(-1)), Nil, UIntType(IntWidth(1)))), + Nil, + uint8 + ) + ) + + val child = WRef("child", BundleType(Seq(Field("out", Default, uint8))), InstanceKind, SourceFlow) + check(Test.ref("child"), child) + check(Test.ref("child").field("out"), + WSubField(child, "out", uint8, SourceFlow) + ) + } + + "IRLookup" should "cache expressions" in { + def mkType(i: Int): String = { + if(i == 0) "UInt<8>" else s"{x: ${mkType(i - 1)}}" + } + + val depth = 500 + + val input = + s"""circuit Test: + | module Test : + | input in: ${mkType(depth)} + | output out: ${mkType(depth)} + | out <= in + |""".stripMargin + + val circuit = new firrtl.stage.transforms.Compiler(Seq(Dependency[ExpandWhensAndCheck])).runTransform( + CircuitState(parse(input), UnknownForm) + ).circuit + val Test = ModuleTarget("Test", "Test") + val irLookup = IRLookup(circuit) + def mkReferences(parent: ReferenceTarget, i: Int): Seq[ReferenceTarget] = { + if(i == 0) Seq(parent) else { + val newParent = parent.field("x") + newParent +: mkReferences(newParent, i - 1) + } + } + + // Check caching from root to leaf + val inRefs = mkReferences(Test.ref("in"), depth) + val (inStartTime, _) = Utils.time(irLookup.expr(inRefs.head)) + inRefs.tail.foreach { r => + val (ms, _) = Utils.time(irLookup.expr(r)) + require(inStartTime > ms) + } + val outRefs = mkReferences(Test.ref("out"), depth).reverse + val (outStartTime, _) = Utils.time(irLookup.expr(outRefs.head)) + outRefs.tail.foreach { r => + val (ms, _) = Utils.time(irLookup.expr(r)) + require(outStartTime > ms) + } + } +} diff --git a/src/test/scala/firrtlTests/transforms/GroupComponentsSpec.scala b/src/test/scala/firrtlTests/transforms/GroupComponentsSpec.scala index 4d38340f..f847fb6c 100644 --- a/src/test/scala/firrtlTests/transforms/GroupComponentsSpec.scala +++ b/src/test/scala/firrtlTests/transforms/GroupComponentsSpec.scala @@ -1,3 +1,5 @@ +// See LICENSE for license details. + package firrtlTests package transforms -- cgit v1.2.3