diff options
Diffstat (limited to 'src')
15 files changed, 439 insertions, 74 deletions
diff --git a/src/main/scala/firrtl/analyses/CircuitGraph.scala b/src/main/scala/firrtl/analyses/CircuitGraph.scala index 426fd012..506bba57 100644 --- a/src/main/scala/firrtl/analyses/CircuitGraph.scala +++ b/src/main/scala/firrtl/analyses/CircuitGraph.scala @@ -3,6 +3,7 @@ package firrtl.analyses import firrtl.Kind +import firrtl.analyses.InstanceKeyGraph.InstanceKey import firrtl.annotations.TargetToken.{Instance, OfModule} import firrtl.annotations._ import firrtl.ir.{Circuit, DefInstance} @@ -48,10 +49,10 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) { private val irLookup = connectionGraph.irLookup // Module/Instance Hierarchy information - private lazy val instanceGraph = new InstanceGraph(circuit) + private lazy val instanceGraph = InstanceKeyGraph(circuit) // Per module, which modules does it instantiate - private lazy val moduleChildren = instanceGraph.getChildrenInstanceOfModule + private lazy val moduleChildren = instanceGraph.getChildInstances.toMap // Top-level module target private val main = ModuleTarget(circuit.main, circuit.main) @@ -80,7 +81,7 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) { */ def absolutePaths(mt: ModuleTarget): Seq[IsModule] = instanceGraph.findInstancesInHierarchy(mt.module).map { case seq if seq.nonEmpty => seq.foldLeft(CircuitTarget(circuit.main).module(circuit.main): IsModule) { - case (it, DefInstance(_, instance, ofModule, _)) => it.instOf(instance, ofModule) + case (it, InstanceKey(instance, ofModule)) => it.instOf(instance, ofModule) } } @@ -113,9 +114,7 @@ class CircuitGraph private[analyses] (connectionGraph: ConnectionGraph) { val leafModule = path.leafModule val children = moduleChildren(leafModule) val localRefs = localReferences(path, kind) - localRefs ++ children.flatMap { - case (Instance(inst), OfModule(ofModule)) => deepReferences(kind, path.instOf(inst, ofModule)) - } + localRefs ++ children.flatMap { child => deepReferences(kind, path.instOf(child.name, child.module)) } } /** Return all absolute references to signals of the given kind directly contained in the module diff --git a/src/main/scala/firrtl/analyses/InstanceGraph.scala b/src/main/scala/firrtl/analyses/InstanceGraph.scala index c0aec4aa..f994b39a 100644 --- a/src/main/scala/firrtl/analyses/InstanceGraph.scala +++ b/src/main/scala/firrtl/analyses/InstanceGraph.scala @@ -25,8 +25,10 @@ import firrtl.annotations.TargetToken._ * Hashing and comparing deep bundle types however is inefficient which can manifest in slower then necessary * lookups and insertions. */ +@deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4") class InstanceGraph(c: Circuit) { + @deprecated("Use InstanceKeyGraph.moduleMap instead.", "FIRRTL 1.4") val moduleMap = c.modules.map({m => (m.name,m) }).toMap private val instantiated = new mutable.LinkedHashSet[String] private val childInstances = @@ -64,11 +66,13 @@ class InstanceGraph(c: Circuit) { * every DefInstance arising from every instance statement in * that module. */ + @deprecated("Use InstanceKeyGraph.graph instead.", "FIRRTL 1.4") lazy val graph = DiGraph(instanceGraph) /** A list of absolute paths (each represented by a Seq of instances) * of all module instances in the Circuit. */ + @deprecated("Use InstanceKeyGraph.fullHierarchy instead.", "FIRRTL 1.4") lazy val fullHierarchy: mutable.LinkedHashMap[DefInstance,Seq[Seq[DefInstance]]] = graph.pathsInDAG(trueTopInstance) /** A count of the *static* number of instances of each module. For any module other than the top (main) module, this is @@ -77,6 +81,7 @@ class InstanceGraph(c: Circuit) { * associated count of one, even though it is never directly instantiated. Any modules *not* instantiated at all will * have a count of zero. */ + @deprecated("Use InstanceKeyGraph.staticInstanceCount instead.", "FIRRTL 1.4") lazy val staticInstanceCount: Map[OfModule, Int] = { val foo = mutable.LinkedHashMap.empty[OfModule, Int] childInstances.keys.foreach { @@ -98,17 +103,20 @@ class InstanceGraph(c: Circuit) { * @param module the name of the selected module * @return a Seq[ Seq[DefInstance] ] of absolute instance paths */ + @deprecated("Use InstanceKeyGraph.findInstancesInHierarchy instead (now with caching of vertices!).", "FIRRTL 1.4") def findInstancesInHierarchy(module: String): Seq[Seq[DefInstance]] = { val instances = graph.getVertices.filter(_.module == module).toSeq instances flatMap { i => fullHierarchy.getOrElse(i, Nil) } } /** An [[firrtl.graph.EulerTour EulerTour]] representation of the [[firrtl.graph.DiGraph DiGraph]] */ + @deprecated("Should have been private. Do not use outside of InstanceGraph.", "FIRRTL 1.4") lazy val tour = EulerTour(graph, trueTopInstance) /** Finds the lowest common ancestor instances for two module names in * a design */ + @deprecated("Use InstanceKeyGraph and EulerTour(iGraph.graph, iGraph.top).rmq(moduleA, moduleB).", "FIRRTL 1.4") def lowestCommonAncestor(moduleA: Seq[DefInstance], moduleB: Seq[DefInstance]): Seq[DefInstance] = { tour.rmq(moduleA, moduleB) @@ -118,6 +126,7 @@ class InstanceGraph(c: Circuit) { * Module order from highest module to leaf module * @return sequence of modules in order from top to leaf */ + @deprecated("Use InstanceKeyGraph.moduleOrder instead.", "FIRRTL 1.4") def moduleOrder: Seq[DefModule] = { graph.transformNodes(_.module).linearize.map(moduleMap(_)) } @@ -126,11 +135,13 @@ class InstanceGraph(c: Circuit) { /** Given a circuit, returns a map from module name to children * instance/module definitions */ + @deprecated("Use InstanceKeyGraph.getChildInstances instead.", "FIRRTL 1.4") def getChildrenInstances: mutable.LinkedHashMap[String, mutable.LinkedHashSet[DefInstance]] = childInstances /** Given a circuit, returns a map from module name to children * instance/module [[firrtl.annotations.TargetToken]]s */ + @deprecated("Use InstanceKeyGraph.getChildInstances instead.", "FIRRTL 1.4") def getChildrenInstanceOfModule: mutable.LinkedHashMap[String, mutable.LinkedHashSet[(Instance, OfModule)]] = childInstances.map(kv => kv._1 -> kv._2.map(_.toTokens)) @@ -146,21 +157,26 @@ class InstanceGraph(c: Circuit) { /** Given a circuit, returns a map from module name to a map * in turn mapping instances names to corresponding module names */ + @deprecated("Use InstanceKeyGraph.getChildInstanceMap instead.", "FIRRTL 1.4") def getChildrenInstanceMap: collection.Map[OfModule, collection.Map[Instance, OfModule]] = childInstances.map(kv => kv._1.OfModule -> asOrderedMap(kv._2, (i: DefInstance) => i.toTokens)) /** The set of all modules in the circuit */ + @deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4") lazy val modules: collection.Set[OfModule] = graph.getVertices.map(_.OfModule) /** The set of all modules in the circuit reachable from the top module */ + @deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4") lazy val reachableModules: collection.Set[OfModule] = mutable.LinkedHashSet(trueTopInstance.OfModule) ++ graph.reachableFrom(trueTopInstance).map(_.OfModule) /** The set of all modules *not* reachable in the circuit */ + @deprecated("Use InstanceKeyGraph.unreachableModules instead.", "FIRRTL 1.4") lazy val unreachableModules: collection.Set[OfModule] = modules diff reachableModules } +@deprecated("Use InstanceKeyGraph instead.", "FIRRTL 1.4") object InstanceGraph { /** Returns all DefInstances in a Statement @@ -169,6 +185,7 @@ object InstanceGraph { * @param s statement to descend * @return */ + @deprecated("Use InstanceKeyGraph.collectInstances instead.", "FIRRTL 1.4") def collectInstances(insts: mutable.Set[DefInstance]) (s: Statement): Unit = s match { case i: DefInstance => insts += i diff --git a/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala b/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala index 49b91788..761315dc 100644 --- a/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala +++ b/src/main/scala/firrtl/analyses/InstanceKeyGraph.scala @@ -4,7 +4,7 @@ package firrtl.analyses import firrtl.annotations._ import firrtl.annotations.TargetToken._ -import firrtl.graph.{DiGraph, MutableDiGraph} +import firrtl.graph.{DiGraph, EulerTour, MutableDiGraph} import firrtl.ir import scala.collection.mutable @@ -14,7 +14,7 @@ import scala.collection.mutable * pairs of InstanceName and Module name as vertex keys instead of using WDefInstance * which will hash the instance type causing some performance issues. */ -class InstanceKeyGraph(c: ir.Circuit) { +class InstanceKeyGraph private(c: ir.Circuit) { import InstanceKeyGraph._ private val nameToModule: Map[String, ir.DefModule] = c.modules.map({m => (m.name,m) }).toMap @@ -23,24 +23,60 @@ class InstanceKeyGraph(c: ir.Circuit) { } private val instantiated = childInstances.flatMap(_._2).map(_.module).toSet private val roots = c.modules.map(_.name).filterNot(instantiated) - private val graph = buildGraph(childInstances, roots) + private val internalGraph = buildGraph(childInstances, roots) private val circuitTopInstance = topKey(c.main) // cache vertices to speed up repeat calls to findInstancesInHierarchy - private lazy val vertices = graph.getVertices + private lazy val vertices = internalGraph.getVertices /** A list of absolute paths (each represented by a Seq of instances) of all module instances in the Circuit. */ - private lazy val fullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] = - graph.pathsInDAG(circuitTopInstance) + private lazy val cachedFullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] = + internalGraph.pathsInDAG(circuitTopInstance) + + /** modules reachable from the main module as well as the main modules itself */ + private lazy val cachedReachableModules: Seq[OfModule] = + circuitTopInstance.OfModule +: internalGraph.reachableFrom(circuitTopInstance).toSeq.map(_.OfModule) + + private lazy val cachedUnreachableModules: Seq[OfModule] = { + val all = mutable.LinkedHashSet(childInstances.map(c => OfModule(c._1)):_*) + val reachable = mutable.LinkedHashSet(cachedReachableModules:_*) + all.diff(reachable).toSeq + } + + /** returns the underlying graph */ + def graph: DiGraph[InstanceKey] = internalGraph + + /** returns the key to the top (main) module */ + def top: InstanceKey = circuitTopInstance /** maps module names to the DefModule node */ def moduleMap: Map[String, ir.DefModule] = nameToModule /** Module order from highest module to leaf module */ - def moduleOrder: Seq[ir.DefModule] = graph.transformNodes(_.module).linearize.map(nameToModule(_)) + def moduleOrder: Seq[ir.DefModule] = internalGraph.transformNodes(_.module).linearize.map(nameToModule(_)) /** Returns a sequence that can be turned into a map from module name to instances defined in said module. */ def getChildInstances: Seq[(String, Seq[InstanceKey])] = childInstances + /** A count of the *static* number of instances of each module. For any module other than the top (main) module, + * this is equivalent to the number of inst statements in the circuit instantiating each module, + * irrespective of the number of times (if any) the enclosing module appears in the hierarchy. + * Note that top module of the circuit has an associated count of one, even though it is never directly instantiated. + * Any modules *not* instantiated at all will have a count of zero. + */ + def staticInstanceCount: Map[OfModule, Int] = cachedStaticInstanceCount + + private lazy val cachedStaticInstanceCount = { + val foo = mutable.LinkedHashMap.empty[OfModule, Int] + childInstances.foreach { + case (main, _) if main == c.main => foo += main.OfModule -> 1 + case (other, _) => foo += other.OfModule -> 0 + } + childInstances.flatMap(_._2).map(_.OfModule).foreach { + mod => foo += mod -> (foo(mod) + 1) + } + foo.toMap + } + /** Finds the absolute paths (each represented by a Seq of instances * representing the chain of hierarchy) of all instances of a particular * module. Note that this includes one implicit instance of the top (main) @@ -52,12 +88,32 @@ class InstanceKeyGraph(c: ir.Circuit) { */ def findInstancesInHierarchy(module: String): Seq[Seq[InstanceKey]] = { val instances = vertices.filter(_.module == module).toSeq - instances.flatMap{ i => fullHierarchy.getOrElse(i, Nil) } + instances.flatMap{ i => cachedFullHierarchy.getOrElse(i, Nil) } } + + /** Given a circuit, returns a map from module name to a map + * in turn mapping instances names to corresponding module names + */ + def getChildInstanceMap: mutable.LinkedHashMap[OfModule, mutable.LinkedHashMap[Instance, OfModule]] = + mutable.LinkedHashMap(childInstances.map { case (k, v) => + val moduleMap: mutable.LinkedHashMap[Instance, OfModule] = mutable.LinkedHashMap(v.map(_.toTokens):_*) + TargetToken.OfModule(k) -> moduleMap + }:_*) + + /** All modules in the circuit reachable from the top module */ + def reachableModules: Seq[OfModule] = cachedReachableModules + + /** All modules *not* reachable from the top module of the circuit */ + def unreachableModules: Seq[OfModule] = cachedUnreachableModules + + /** A list of absolute paths (each represented by a Seq of instances) of all module instances in the Circuit. */ + def fullHierarchy: mutable.LinkedHashMap[InstanceKey, Seq[Seq[InstanceKey]]] = cachedFullHierarchy } object InstanceKeyGraph { + def apply(c: ir.Circuit): InstanceKeyGraph = new InstanceKeyGraph(c) + /** We want to only use this untyped version as key because hashing bundle types is expensive * @param name the name of the instance * @param module the name of the module that is instantiated diff --git a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala index 402f7028..d92d3b5e 100644 --- a/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala +++ b/src/main/scala/firrtl/annotations/transforms/EliminateTargetPaths.scala @@ -3,7 +3,7 @@ package firrtl.annotations.transforms import firrtl.Mappers._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import firrtl.annotations.ModuleTarget import firrtl.annotations.TargetToken.{Instance, OfModule, fromDefModuleToTargetToken} import firrtl.annotations.analysis.DuplicationHelper @@ -132,7 +132,7 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration { */ def run(cir: Circuit, targets: Seq[IsMember], - iGraph: InstanceGraph + iGraph: InstanceKeyGraph ): (Circuit, RenameMap, AnnotationSeq) = { val dupMap = DuplicationHelper(cir.modules.map(_.name).toSet) @@ -239,8 +239,8 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration { val targets = targetsToEliminate.collect { case x: IsMember => x } // Check validity of paths in targets - val iGraph = new InstanceGraph(state.circuit) - val instanceOfModules = iGraph.getChildrenInstanceOfModule + val iGraph = InstanceKeyGraph(state.circuit) + val instanceOfModules = iGraph.getChildInstances.map { case(k,v) => k -> v.map(_.toTokens) }.toMap val targetsWithInvalidPaths = mutable.ArrayBuffer[IsMember]() targets.foreach { t => val path = t match { @@ -311,8 +311,8 @@ class EliminateTargetPaths extends Transform with DependencyAPIMigration { nextRenameMap } - val iGraphx = new InstanceGraph(newCircuit) - val newlyUnreachableModules = iGraphx.unreachableModules diff iGraph.unreachableModules + val iGraphx = InstanceKeyGraph(newCircuit) + val newlyUnreachableModules = iGraphx.unreachableModules.toSet diff iGraph.unreachableModules.toSet val newCircuitGC = { val modulesx = newCircuit.modules.flatMap{ diff --git a/src/main/scala/firrtl/passes/Inline.scala b/src/main/scala/firrtl/passes/Inline.scala index 39cb4b9c..ad963b19 100644 --- a/src/main/scala/firrtl/passes/Inline.scala +++ b/src/main/scala/firrtl/passes/Inline.scala @@ -7,7 +7,7 @@ import firrtl.ir._ import firrtl.Mappers._ import firrtl.annotations._ import firrtl.annotations.TargetToken.{Instance, OfModule} -import firrtl.analyses.{InstanceGraph} +import firrtl.analyses.InstanceKeyGraph import firrtl.graph.{DiGraph, MutableDiGraph} import firrtl.stage.{Forms, RunFirrtlTransformAnnotation} import firrtl.options.{RegisteredTransform, ShellOption} @@ -80,7 +80,7 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe // 3) All annotated instances exist, and their modules can be inline def check(c: Circuit, moduleNames: Set[ModuleName], instanceNames: Set[ComponentName]): Unit = { val errors = mutable.ArrayBuffer[PassException]() - val moduleMap = new InstanceGraph(c).moduleMap + val moduleMap = InstanceKeyGraph(c).moduleMap def checkExists(name: String): Unit = if (!moduleMap.contains(name)) errors += new PassException(s"Annotated module does not exist: $name") @@ -136,10 +136,10 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe check(c, modsToInline, instsToInline) val flatModules = modsToInline.map(m => m.name) val flatInstances: Set[(OfModule, Instance)] = instsToInline.map(i => OfModule(i.module.name) -> Instance(i.name)) ++ getInstancesOf(c, flatModules) - val iGraph = new InstanceGraph(c) + val iGraph = InstanceKeyGraph(c) val namespaceMap = collection.mutable.Map[String, Namespace]() // Map of Module name to Map of instance name to Module name - val instMaps = iGraph.getChildrenInstanceMap + val instMaps = iGraph.getChildInstanceMap /** Add a prefix to all declarations updating a [[Namespace]] and appending to a [[RenameMap]] */ def appendNamePrefix( diff --git a/src/main/scala/firrtl/passes/wiring/Wiring.scala b/src/main/scala/firrtl/passes/wiring/Wiring.scala index c62a565e..3f74e5d2 100644 --- a/src/main/scala/firrtl/passes/wiring/Wiring.scala +++ b/src/main/scala/firrtl/passes/wiring/Wiring.scala @@ -5,11 +5,14 @@ package wiring import firrtl._ import firrtl.ir._ + import scala.collection.mutable import firrtl.annotations._ import firrtl.annotations.AnnotationUtils._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import WiringUtils._ +import firrtl.analyses.InstanceKeyGraph.InstanceKey +import firrtl.graph.EulerTour /** A data store of one sink--source wiring relationship */ case class WiringInfo(source: ComponentName, sinks: Seq[Named], pin: String) @@ -47,7 +50,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { else ns.newName(tokenize(c) filterNot ("[]." contains _) mkString "_") })}} - val iGraph = new InstanceGraph(c) + val iGraph = InstanceKeyGraph(c) names.zip(portNames).map{ case(WiringNames(comp, so, si, _), pn) => computeModifications(c, iGraph, comp, so, si, pn) } } @@ -67,7 +70,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { * to pending modifications */ private def computeModifications(c: Circuit, - iGraph: InstanceGraph, + iGraph: InstanceKeyGraph, compName: String, source: String, sinks: Seq[Named], @@ -94,12 +97,17 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { def makeWireC(m: Modifications, portName: String, c: (String, String)): Modifications = m.copy(addPortOrWire = Some(m.addPortOrWire.getOrElse((portName, DecWire))), cons = (m.cons :+ c).distinct ) + val tour = EulerTour(iGraph.graph, iGraph.top) + // Finds the lowest common ancestor instances for two module names in a design + def lowestCommonAncestor(moduleA: Seq[InstanceKey], moduleB: Seq[InstanceKey]): Seq[InstanceKey] = + tour.rmq(moduleA, moduleB) + owners.foreach { case (sink, source) => - val lca = iGraph.lowestCommonAncestor(sink, source) + val lca = lowestCommonAncestor(sink, source) // Compute metadata along Sink to LCA paths. sink.drop(lca.size - 1).sliding(2).toList.reverse.foreach { - case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) => + case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) => val to = s"$ci.${portNames(cm)}" val from = s"${portNames(pm)}" meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from)) @@ -107,12 +115,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { addPortOrWire = Some((portNames(cm), DecInput)) ) // Case where the sink is the LCA - case Seq(WDefInstance(_,_,pm,_)) => + case Seq(InstanceKey(_,pm)) => // Case where the source is also the LCA if (source.drop(lca.size).isEmpty) { meta(pm) = makeWire(meta(pm), portNames(pm)) } else { - val WDefInstance(_,ci,cm,_) = source.drop(lca.size).head + val InstanceKey(ci,cm) = source.drop(lca.size).head val to = s"${portNames(pm)}" val from = s"$ci.${portNames(cm)}" meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from)) @@ -120,7 +128,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { } // Compute metadata for the Sink - sink.last match { case WDefInstance(_, _, m, _) => + sink.last match { case InstanceKey( _, m) => if (sinkComponents.contains(m)) { val from = s"${portNames(m)}" sinkComponents(m).foreach( to => @@ -132,7 +140,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { } // Compute metadata for the Source - source.last match { case WDefInstance(_, _, m, _) => + source.last match { case InstanceKey( _, m) => val to = s"${portNames(m)}" val from = compName meta(m) = meta(m).copy( @@ -142,7 +150,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { // Compute metadata along Source to LCA path source.drop(lca.size - 1).sliding(2).toList.reverse.map { - case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) => { + case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) => { val to = s"${portNames(pm)}" val from = s"$ci.${portNames(cm)}" meta(pm) = meta(pm).copy( @@ -153,12 +161,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { ) } // Case where the source is the LCA - case Seq(WDefInstance(_,_,pm,_)) => { + case Seq(InstanceKey(_,pm)) => { // Case where the sink is also the LCA. We do nothing here, // as we've created the connecting wire above if (sink.drop(lca.size).isEmpty) { } else { - val WDefInstance(_,ci,cm,_) = sink.drop(lca.size).head + val InstanceKey(ci,cm) = sink.drop(lca.size).head val to = s"$ci.${portNames(cm)}" val from = s"${portNames(pm)}" meta(pm) = meta(pm).copy( diff --git a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala index 5f09bbe0..c220692a 100644 --- a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala +++ b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala @@ -7,11 +7,13 @@ import firrtl._ import firrtl.ir._ import firrtl.Utils._ import firrtl.Mappers._ +import firrtl.analyses.InstanceKeyGraph.InstanceKey import firrtl.traversals.Foreachers._ + import scala.collection.mutable import firrtl.annotations._ import firrtl.annotations.AnnotationUtils._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.{InstanceGraph, InstanceKeyGraph} /** Declaration kind in lineage (e.g. input port, output port, wire) */ @@ -112,9 +114,66 @@ object WiringUtils { * @return a map of sink instance names to source instance names * @throws WiringException if a sink is equidistant to two sources */ - @deprecated("This method can lead to non-determinism in your compiler pass. Use sinksToSourcesSeq instead!", "Firrtl 1.4") - def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] = - sinksToSourcesSeq(sinks, source, i).toMap + @deprecated("This method can lead to non-determinism in your compiler pass and exposes internal details." + + " Please file an issue with firrtl if you have a use case!", "Firrtl 1.4") + def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] = { + // The order of owners influences the order of the results, it thus needs to be deterministic with a LinkedHashMap. + val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]] + val queue = new mutable.Queue[Seq[WDefInstance]] + val visited = new mutable.HashMap[Seq[WDefInstance], Boolean].withDefaultValue(false) + + val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source => v } + sourcePaths.flatten.foreach { l => + queue.enqueue(l) + owners(l) = Vector(l) + } + + val sinkModuleNames = sinks.map(getModuleName).toSet + val sinkPaths = i.fullHierarchy.collect { case (k,v) if sinkModuleNames.contains(k.module) => v } + // sinkInsts needs to have unique entries but is also iterated over which is why we use a LinkedHashSet + val sinkInsts = mutable.LinkedHashSet() ++ sinkPaths.flatten + + /** If we're lucky and there is only one source, then that source owns + * all sinks. If we're unlucky, we need to do a full (slow) BFS + * to figure out who owns what. Currently, the BFS is not + * performant. + * + * [todo] The performance of this will need to be improved. + * Possible directions are that if we're purely source-under-sink + * or sink-under-source, then ownership is trivially a mapping + * down/up. Ownership seems to require a BFS if we have + * sources/sinks not under sinks/sources. + */ + if (queue.size == 1) { + val u = queue.dequeue + sinkInsts.foreach { v => owners(v) = Vector(u) } + } else { + while (queue.nonEmpty) { + val u = queue.dequeue + visited(u) = true + + val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1)) + + // [todo] This is the critical section + edges + .filter( e => !visited(e) && e.nonEmpty ) + .foreach{ v => + owners(v) = owners.getOrElse(v, Vector()) ++ owners(u) + queue.enqueue(v) + } + } + + // Check that every sink has one unique owner. The only time that + // this should fail is if a sink is equidistant to two sources. + sinkInsts.foreach { s => + if (!owners.contains(s) || owners(s).size > 1) { + throw new WiringException( + s"Unable to determine source mapping for sink '${s.map(_.name)}'") } + } + } + + owners.collect { case (k, v) if sinkInsts.contains(k) => (k, v.flatten) }.toMap + } /** Return a map of sink instances to source instances that minimizes * distance @@ -125,15 +184,12 @@ object WiringUtils { * @return a map of sink instance names to source instance names * @throws WiringException if a sink is equidistant to two sources */ - def sinksToSourcesSeq(sinks: Seq[Named], - source: String, - i: InstanceGraph): - Seq[(Seq[WDefInstance], Seq[WDefInstance])] = { + private[firrtl] def sinksToSourcesSeq(sinks: Seq[Named], source: String, i: InstanceKeyGraph): + Seq[(Seq[InstanceKey], Seq[InstanceKey])] = { // The order of owners influences the order of the results, it thus needs to be deterministic with a LinkedHashMap. - val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]] - val queue = new mutable.Queue[Seq[WDefInstance]] - val visited = new mutable.HashMap[Seq[WDefInstance], Boolean] - .withDefaultValue(false) + val owners = new mutable.LinkedHashMap[Seq[InstanceKey], Vector[Seq[InstanceKey]]] + val queue = new mutable.Queue[Seq[InstanceKey]] + val visited = new mutable.HashMap[Seq[InstanceKey], Boolean].withDefaultValue(false) val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source => v } sourcePaths.flatten.foreach { l => @@ -165,7 +221,7 @@ object WiringUtils { val u = queue.dequeue visited(u) = true - val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1)) + val edges = i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1) // [todo] This is the critical section edges diff --git a/src/main/scala/firrtl/transforms/CheckCombLoops.scala b/src/main/scala/firrtl/transforms/CheckCombLoops.scala index dbfd5cf8..6403be23 100644 --- a/src/main/scala/firrtl/transforms/CheckCombLoops.scala +++ b/src/main/scala/firrtl/transforms/CheckCombLoops.scala @@ -11,7 +11,7 @@ import firrtl.traversals.Foreachers._ import firrtl.annotations._ import firrtl.Utils.throwInternalError import firrtl.graph._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import firrtl.options.{Dependency, RegisteredTransform, ShellOption} /** @@ -241,7 +241,7 @@ class CheckCombLoops extends Transform case ann: Annotation => CircuitTarget(c.main) } val moduleMap = c.modules.map({m => (m.name,m) }).toMap - val iGraph = new InstanceGraph(c).graph + val iGraph = InstanceKeyGraph(c).graph val moduleDeps = iGraph.getEdgeMap.map({ case (k,v) => (k.module, (v map { i => (i.name, i.module) }).toMap) }).toMap val topoSortedModules = iGraph.transformNodes(_.module).linearize.reverse map { moduleMap(_) } val moduleGraphs = new mutable.HashMap[String, ConnMap] diff --git a/src/main/scala/firrtl/transforms/ConstantPropagation.scala b/src/main/scala/firrtl/transforms/ConstantPropagation.scala index c3c615e0..ce36dd72 100644 --- a/src/main/scala/firrtl/transforms/ConstantPropagation.scala +++ b/src/main/scala/firrtl/transforms/ConstantPropagation.scala @@ -11,7 +11,7 @@ import firrtl.Utils._ import firrtl.Mappers._ import firrtl.PrimOps._ import firrtl.graph.DiGraph -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import firrtl.annotations.TargetToken.Ref import firrtl.options.Dependency @@ -739,8 +739,8 @@ class ConstantPropagation extends Transform with DependencyAPIMigration with Res private def run(c: Circuit, dontTouchMap: Map[OfModule, Set[String]]): Circuit = { - val iGraph = new InstanceGraph(c) - val moduleDeps = iGraph.getChildrenInstanceMap + val iGraph = InstanceKeyGraph(c) + val moduleDeps = iGraph.getChildInstanceMap val instCount = iGraph.staticInstanceCount // DiGraph using Module names as nodes, destination of edge is a parent Module diff --git a/src/main/scala/firrtl/transforms/DeadCodeElimination.scala b/src/main/scala/firrtl/transforms/DeadCodeElimination.scala index f9e35818..c883bdfb 100644 --- a/src/main/scala/firrtl/transforms/DeadCodeElimination.scala +++ b/src/main/scala/firrtl/transforms/DeadCodeElimination.scala @@ -6,7 +6,7 @@ import firrtl.ir._ import firrtl.passes._ import firrtl.annotations._ import firrtl.graph._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import firrtl.Mappers._ import firrtl.Utils.{throwInternalError, kind} import firrtl.MemoizedHash._ @@ -314,7 +314,7 @@ class DeadCodeElimination extends Transform doTouchExtMods: Set[String]): CircuitState = { val c = state.circuit val moduleMap = c.modules.map(m => m.name -> m).toMap - val iGraph = new InstanceGraph(c) + val iGraph = InstanceKeyGraph(c) val moduleDeps = iGraph.graph.getEdgeMap.map({ case (k,v) => k.module -> v.map(i => i.name -> i.module).toMap }) diff --git a/src/main/scala/firrtl/transforms/Dedup.scala b/src/main/scala/firrtl/transforms/Dedup.scala index 30558129..627af11f 100644 --- a/src/main/scala/firrtl/transforms/Dedup.scala +++ b/src/main/scala/firrtl/transforms/Dedup.scala @@ -157,7 +157,7 @@ class DedupModules extends Transform with DependencyAPIMigration { moduleRenameMap.recordAll(map) // Build instanceify renaming map - val instanceGraph = new InstanceKeyGraph(c) + val instanceGraph = InstanceKeyGraph(c) val instanceify = RenameMap() val moduleName2Index = c.modules.map(_.name).zipWithIndex.map { case (n, i) => { @@ -467,7 +467,7 @@ object DedupModules extends LazyLogging { renameMap: RenameMap): Map[String, DefModule] = { val (moduleMap, moduleLinearization) = { - val iGraph = new InstanceKeyGraph(circuit) + val iGraph = InstanceKeyGraph(circuit) (iGraph.moduleMap, iGraph.moduleOrder.reverse) } val main = circuit.main diff --git a/src/main/scala/firrtl/transforms/ManipulateNames.scala b/src/main/scala/firrtl/transforms/ManipulateNames.scala index ea988e72..f15b546f 100644 --- a/src/main/scala/firrtl/transforms/ManipulateNames.scala +++ b/src/main/scala/firrtl/transforms/ManipulateNames.scala @@ -3,7 +3,7 @@ package firrtl.transforms import firrtl._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import firrtl.Mappers._ import firrtl.annotations.{ @@ -422,7 +422,7 @@ abstract class ManipulateNames[A <: ManipulateNames[_] : ClassTag] extends Trans * roots ensures that the rename map is safe for parents to blindly consult. Store this in mapping of old module * target to new module to allow the modules to be put in the old order. */ - val modulesx: Map[ModuleTarget, ir.DefModule] = new InstanceGraph(c).moduleOrder.reverse + val modulesx: Map[ModuleTarget, ir.DefModule] = InstanceKeyGraph(c).moduleOrder.reverse .map(m => t.module(m.name) -> onModule(m, r, t)) .toMap diff --git a/src/main/scala/firrtl/transforms/RenameModules.scala b/src/main/scala/firrtl/transforms/RenameModules.scala index edd9fefb..d37f8c39 100644 --- a/src/main/scala/firrtl/transforms/RenameModules.scala +++ b/src/main/scala/firrtl/transforms/RenameModules.scala @@ -2,7 +2,7 @@ package firrtl.transforms -import firrtl.analyses.{InstanceGraph, ModuleNamespaceAnnotation} +import firrtl.analyses.{InstanceKeyGraph, ModuleNamespaceAnnotation} import firrtl.ir._ import firrtl._ import firrtl.stage.Forms @@ -39,7 +39,7 @@ class RenameModules extends Transform with DependencyAPIMigration { logger.warn("Skipping Rename Modules") state } else { - val moduleOrder = new InstanceGraph(state.circuit).moduleOrder.reverse + val moduleOrder = InstanceKeyGraph(state.circuit).moduleOrder.reverse val nameMappings = new mutable.HashMap[String, String]() moduleOrder.foreach(collectNameMapping(namespace.get, nameMappings)) diff --git a/src/main/scala/firrtl/transforms/TopWiring.scala b/src/main/scala/firrtl/transforms/TopWiring.scala index 59c494c7..aa046770 100644 --- a/src/main/scala/firrtl/transforms/TopWiring.scala +++ b/src/main/scala/firrtl/transforms/TopWiring.scala @@ -4,9 +4,10 @@ package TopWiring import firrtl._ import firrtl.ir._ -import firrtl.passes.{InferTypes, LowerTypes, ResolveKinds, ResolveFlows, ExpandConnects} +import firrtl.passes.{ExpandConnects, InferTypes, LowerTypes, ResolveFlows, ResolveKinds} import firrtl.annotations._ import firrtl.Mappers._ +import firrtl.analyses.InstanceKeyGraph import firrtl.stage.Forms import firrtl.options.Dependency @@ -129,8 +130,8 @@ class TopWiringTransform extends Transform with DependencyAPIMigration { private def getSourcesMap(state: CircuitState): Map[String,Seq[(ComponentName, Type, Boolean, InstPath, String)]] = { val sSourcesModNames = getSourceModNames(state) val sSourcesNames = getSourceNames(state) - val instGraph = new firrtl.analyses.InstanceGraph(state.circuit) - val cMap = instGraph.getChildrenInstances.map{ case (m, wdis) => + val instGraph = firrtl.analyses.InstanceKeyGraph(state.circuit) + val cMap = instGraph.getChildInstances.map{ case (m, wdis) => (m -> wdis.map{ case wdi => (wdi.name, wdi.module) }.toSeq) }.toMap val topSort = instGraph.moduleOrder.reverse @@ -167,7 +168,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration { */ private def onModule(sources: Map[String, Seq[(ComponentName, Type, Boolean, InstPath, String)]], portnamesmap : mutable.Map[String,String], - instgraph : firrtl.analyses.InstanceGraph, + instgraph : firrtl.analyses.InstanceKeyGraph, namespacemap : Map[String, Namespace]) (module: DefModule): DefModule = { val namespace = namespacemap(module.name) @@ -186,6 +187,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration { } } // Add connections to Module + val childInstances = instgraph.getChildInstances.toMap module match { case m: Module => val connections: Seq[Connect] = p.map { case (ComponentName(cname,_), _, _ , path, prefix) => @@ -205,7 +207,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration { val instportname = portnamesmap.get(prefix + path.tail.mkString("_")) match { case Some(ipn) => ipn case None => { - val instmod = instgraph.getChildrenInstances(module.name).collectFirst { + val instmod = childInstances(module.name).collectFirst { case wdi if wdi.name == path.head => wdi.module}.get val instnamespace = namespacemap(instmod) portnamesmap(prefix + path.tail.mkString("_")) = @@ -244,7 +246,7 @@ class TopWiringTransform extends Transform with DependencyAPIMigration { val sources = getSourcesMap(state) val (nstate, nmappings) = if (sources.nonEmpty) { val portnamesmap: mutable.Map[String,String] = mutable.Map() - val instgraph = new firrtl.analyses.InstanceGraph(state.circuit) + val instgraph = InstanceKeyGraph(state.circuit) val namespacemap = state.circuit.modules.map{ case m => (m.name -> Namespace(m)) }.toMap val modulesx = state.circuit.modules map onModule(sources, portnamesmap, instgraph, namespacemap) val newCircuit = state.circuit.copy(modules = modulesx) diff --git a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala index 8d073ecb..ec403259 100644 --- a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala +++ b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala @@ -4,10 +4,105 @@ package firrtlTests.analyses import firrtl.analyses.InstanceKeyGraph import firrtl.analyses.InstanceKeyGraph.InstanceKey +import firrtl.annotations.TargetToken.OfModule +import firrtl.graph.DiGraph import firrtl.testutils.FirrtlFlatSpec class InstanceKeyGraphSpec extends FirrtlFlatSpec { - behavior of "InstanceKeyGraph" + behavior of "InstanceKeyGraph.graph" + + private def getEdgeSet(graph: DiGraph[String]): collection.Map[String, collection.Set[String]] = { + (graph.getVertices map {v => (v, graph.getEdges(v))}).toMap + } + + it should "recognize a simple hierarchy" in { + val input = + """circuit Top : + | module Top : + | inst c1 of Child1 + | inst c2 of Child2 + | module Child1 : + | inst a of Child1a + | inst b of Child1b + | skip + | module Child1a : + | skip + | module Child1b : + | skip + | module Child2 : + | skip + |""".stripMargin + + val graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module) + getEdgeSet(graph) shouldBe Map( + "Top" -> Set("Child1", "Child2"), + "Child1" -> Set("Child1a", "Child1b"), + "Child2" -> Set(), "Child1a" -> Set(), "Child1b" -> Set()) + } + + it should "recognize disconnected hierarchies" in { + val input = + """circuit Top : + | module Top : + | inst c of Child1 + | module Child1 : + | skip + | + | module Top2 : + | inst a of Child2 + | inst b of Child3 + | skip + | module Child2 : + | inst a of Child2a + | inst b of Child2b + | skip + | module Child2a : + | skip + | module Child2b : + | skip + | module Child3 : + | skip + |""".stripMargin + + val graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module) + getEdgeSet(graph) shouldBe Map( + "Top" -> Set("Child1"), + "Top2" -> Set("Child2", "Child3"), + "Child2" -> Set("Child2a", "Child2b"), + "Child1" -> Set(), "Child2a" -> Set(), "Child2b" -> Set(), "Child3" -> Set()) + } + + it should "not drop duplicate nodes when they collide as a result of transformNodes" in { + val input = + """circuit Top : + | module Buzz : + | skip + | module Fizz : + | inst b of Buzz + | module Foo : + | inst f1 of Fizz + | module Bar : + | inst f2 of Fizz + | module Top : + | inst f of Foo + | inst b of Bar + |""".stripMargin + val graph = InstanceKeyGraph(parse(input)).graph + + // Create graphs with edges from child to parent module + // g1 has collisions on parents to children, ie. it combines: + // (f1, Fizz) -> (b, Buzz) and (f2, Fizz) -> (b, Buzz) + val g1 = graph.transformNodes(_.module).reverse + g1.getEdges("Fizz") shouldBe Set("Foo", "Bar") + + val g2 = graph.reverse.transformNodes(_.module) + // g2 combines + // (f1, Fizz) -> (f, Foo) and (f2, Fizz) -> (b, Bar) + g2.getEdges("Fizz") shouldBe Set("Foo", "Bar") + } + + + behavior of "InstanceKeyGraph.getChildInstances" // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to // experience non-determinism @@ -29,7 +124,7 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec { | skip |""".stripMargin val circuit = parse(input) - val instGraph = new InstanceKeyGraph(circuit) + val instGraph = InstanceKeyGraph(circuit) val childMap = instGraph.getChildInstances childMap.map(_._1) should equal (Seq("Top", "Child1", "Child1a", "Child1b", "Child2")) } @@ -50,12 +145,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec { | skip |""".stripMargin val circuit = parse(input) - val instGraph = new InstanceKeyGraph(circuit) + val instGraph = InstanceKeyGraph(circuit) val childMap = instGraph.getChildInstances.toMap val insts = childMap("Top").map(_.name) insts should equal (Seq("a", "b", "c", "d", "e", "f")) } + behavior of "InstanceKeyGraph.moduleOrder" + it should "compute a correct and deterministic module order" in { val input = """ |circuit Top : @@ -80,12 +177,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec { | skip |""".stripMargin val circuit = parse(input) - val instGraph = new InstanceKeyGraph(circuit) + val instGraph = InstanceKeyGraph(circuit) val order = instGraph.moduleOrder.map(_.name) // Where it has freedom, the instance declaration order will be reversed. order should equal (Seq("Top", "Child3", "Child4", "Child2", "Child1", "Child1b", "Child1a")) } + behavior of "InstanceKeyGraph.findInstancesInHierarchy" + it should "find hierarchical instances correctly in disconnected hierarchies" in { val input = """circuit Top : @@ -111,9 +210,10 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec { |""".stripMargin val circuit = parse(input) - val iGraph = new InstanceKeyGraph(circuit) + val iGraph = InstanceKeyGraph(circuit) iGraph.findInstancesInHierarchy("Top") shouldBe Seq(Seq(InstanceKey("Top", "Top"))) - iGraph.findInstancesInHierarchy("Child1") shouldBe Seq(Seq(InstanceKey("Top", "Top"), InstanceKey("c", "Child1"))) + iGraph.findInstancesInHierarchy("Child1") shouldBe + Seq(Seq(InstanceKey("Top", "Top"), InstanceKey("c", "Child1"))) iGraph.findInstancesInHierarchy("Top2") shouldBe Nil iGraph.findInstancesInHierarchy("Child2") shouldBe Nil iGraph.findInstancesInHierarchy("Child2a") shouldBe Nil @@ -121,4 +221,131 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec { iGraph.findInstancesInHierarchy("Child3") shouldBe Nil } + behavior of "InstanceKeyGraph.staticInstanceCount" + + it should "report that there is one instance of the top module" in { + val input = + """|circuit Foo: + | module Foo: + | skip + |""".stripMargin + val iGraph = InstanceKeyGraph(parse(input)) + val expectedCounts = Map(OfModule("Foo") -> 1) + iGraph.staticInstanceCount should be (expectedCounts) + } + + it should "report correct number of instances for a sample circuit" in { + val input = + """|circuit Foo: + | module Baz: + | skip + | module Bar: + | inst baz1 of Baz + | inst baz2 of Baz + | inst baz3 of Baz + | skip + | module Foo: + | inst bar1 of Bar + | inst bar2 of Bar + |""".stripMargin + val iGraph = InstanceKeyGraph(parse(input)) + val expectedCounts = Map(OfModule("Foo") -> 1, + OfModule("Bar") -> 2, + OfModule("Baz") -> 3) + iGraph.staticInstanceCount should be (expectedCounts) + } + + it should "report zero instances for dead modules" in { + val input = + """|circuit Foo: + | module Bar: + | skip + | module Foo: + | skip + |""".stripMargin + val iGraph = InstanceKeyGraph(parse(input)) + val expectedCounts = Map(OfModule("Foo") -> 1, + OfModule("Bar") -> 0) + iGraph.staticInstanceCount should be (expectedCounts) + } + + behavior of "InstanceKeyGraph.getChildInstanceMap" + + it should "preserve Module declaration order" in { + val input = """ + |circuit Top : + | module Top : + | inst c1 of Child1 + | inst c2 of Child2 + | inst c3 of Child1 + | inst c4 of Child1 + | inst c5 of Child1 + | module Child1 : + | inst a of Child1a + | inst b of Child1b + | skip + | module Child1a : + | skip + | module Child1b : + | skip + | module Child2 : + | skip + |""".stripMargin + val circuit = parse(input) + val instGraph = InstanceKeyGraph(circuit) + val childMap = instGraph.getChildInstanceMap + + val modules = childMap.keys.toSeq.map(_.value) + assert(modules == Seq("Top", "Child1", "Child1a", "Child1b", "Child2")) + + assert(childMap(OfModule("Child1a")).isEmpty) + assert(childMap(OfModule("Child1b")).isEmpty) + assert(childMap(OfModule("Child2")).isEmpty) + + val topInstances = childMap(OfModule("Top")).map { case (k,v) => k.value -> v.value}.toSeq + assert(topInstances == + Seq("c1" -> "Child1", "c2" -> "Child2", "c3" -> "Child1", "c4" -> "Child1", "c5" -> "Child1")) + + val child1Instance = childMap(OfModule("Child1")).map { case (k,v) => k.value -> v.value}.toSeq + assert(child1Instance == Seq("a" -> "Child1a", "b" -> "Child1b")) + } + + behavior of "InstanceKeyGraph.fullHierarchy" + + // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to + // experience non-determinism + it should "have defined fullHierarchy order" in { + val input = + """circuit Top : + | module Top : + | inst a of Child + | inst b of Child + | inst c of Child + | inst d of Child + | inst e of Child + | module Child : + | skip + |""".stripMargin + + val instGraph = InstanceKeyGraph(parse(input)) + val hier = instGraph.fullHierarchy + hier.keys.toSeq.map(_.name) should equal (Seq("Top", "a", "b", "c", "d", "e")) + } + + behavior of "Reachable/Unreachable helper methods" + + they should "report correct reachable/unreachable counts" in { + val input = + """|circuit Top: + | module Unreachable: + | skip + | module Reachable: + | skip + | module Top: + | inst reachable of Reachable + |""".stripMargin + val iGraph = InstanceKeyGraph(parse(input)) + iGraph.reachableModules should contain theSameElementsAs Seq(OfModule("Top"), OfModule("Reachable")) + iGraph.unreachableModules should contain theSameElementsAs Seq(OfModule("Unreachable")) + } } |