From 6ea4ac666e4ce8dfaca1545660f372fccff610f5 Mon Sep 17 00:00:00 2001 From: Adam Izraelevitz Date: Wed, 21 Mar 2018 14:24:25 -0700 Subject: GroupModule Transform (#766) * Added grouping pass * Added InfoMagnet and infomappers * Changed return type of execute to allow final CircuitState inspection * Updated dedup. Now is name-agnostic * Added GroupAndDedup transform--- src/main/scala/firrtl/analyses/InstanceGraph.scala | 115 +++++++++++++++++++++ src/main/scala/firrtl/analyses/Netlist.scala | 97 ----------------- 2 files changed, 115 insertions(+), 97 deletions(-) create mode 100644 src/main/scala/firrtl/analyses/InstanceGraph.scala delete mode 100644 src/main/scala/firrtl/analyses/Netlist.scala (limited to 'src/main/scala/firrtl/analyses') diff --git a/src/main/scala/firrtl/analyses/InstanceGraph.scala b/src/main/scala/firrtl/analyses/InstanceGraph.scala new file mode 100644 index 00000000..29942cd5 --- /dev/null +++ b/src/main/scala/firrtl/analyses/InstanceGraph.scala @@ -0,0 +1,115 @@ +// See LICENSE for license details. + +package firrtl.analyses + +import scala.collection.mutable + +import firrtl._ +import firrtl.ir._ +import firrtl.graph._ +import firrtl.Utils._ +import firrtl.Mappers._ + + +/** A class representing the instance hierarchy of a working IR Circuit + * + * @constructor constructs an instance graph from a Circuit + * @param c the Circuit to analyze + */ +class InstanceGraph(c: Circuit) { + + private val moduleMap = c.modules.map({m => (m.name,m) }).toMap + private val instantiated = new mutable.HashSet[String] + private val childInstances = + new mutable.HashMap[String,mutable.Set[WDefInstance]] + for (m <- c.modules) { + childInstances(m.name) = new mutable.HashSet[WDefInstance] + m map InstanceGraph.collectInstances(childInstances(m.name)) + instantiated ++= childInstances(m.name).map(i => i.module) + } + + private val uninstantiated = moduleMap.keySet -- instantiated + private val instanceGraph = new MutableDiGraph[WDefInstance] + private val instanceQueue = new mutable.Queue[WDefInstance] + + uninstantiated.foreach({ subTop => + val topInstance = WDefInstance(subTop,subTop) + instanceQueue.enqueue(topInstance) + while (instanceQueue.nonEmpty) { + val current = instanceQueue.dequeue + instanceGraph.addVertex(current) + for (child <- childInstances(current.module)) { + if (!instanceGraph.contains(child)) { + instanceQueue.enqueue(child) + instanceGraph.addVertex(child) + } + instanceGraph.addEdge(current,child) + } + } + }) + + // The true top module (circuit main) + private val trueTopInstance = WDefInstance(c.main, c.main) + + /** A directed graph showing the instance dependencies among modules + * in the circuit. Every WDefInstance of a module has an edge to + * every WDefInstance arising from every instance statement in + * that module. + */ + lazy val graph = DiGraph(instanceGraph) + + /** A list of absolute paths (each represented by a Seq of instances) + * of all module instances in the Circuit. + */ + lazy val fullHierarchy: collection.Map[WDefInstance,Seq[Seq[WDefInstance]]] = graph.pathsInDAG(trueTopInstance) + + /** Finds the absolute paths (each represented by a Seq of instances + * representing the chain of hierarchy) of all instances of a + * particular module. + * + * @param module the name of the selected module + * @return a Seq[ Seq[WDefInstance] ] of absolute instance paths + */ + def findInstancesInHierarchy(module: String): Seq[Seq[WDefInstance]] = { + val instances = graph.getVertices.filter(_.module == module).toSeq + instances flatMap { i => fullHierarchy(i) } + } + + /** An `[[EulerTour]]` representation of the `[[DiGraph]]` */ + lazy val tour = EulerTour(graph, trueTopInstance) + + /** Finds the lowest common ancestor instances for two module names in + * a design + */ + def lowestCommonAncestor(moduleA: Seq[WDefInstance], + moduleB: Seq[WDefInstance]): Seq[WDefInstance] = { + tour.rmq(moduleA, moduleB) + } + + /** + * Module order from highest module to leaf module + * @return sequence of modules in order from top to leaf + */ + def moduleOrder: Seq[DefModule] = { + graph.transformNodes(_.module).linearize.map(moduleMap(_)) + } +} + +object InstanceGraph { + + /** Returns all WDefInstances in a Statement + * + * @param insts mutable datastructure to append to + * @param s statement to descend + * @return + */ + def collectInstances(insts: mutable.Set[WDefInstance]) + (s: Statement): Statement = s match { + case i: WDefInstance => + insts += i + i + case i: DefInstance => throwInternalError(Some("Expecting WDefInstance, found a DefInstance!")) + case i: WDefInstanceConnector => throwInternalError(Some("Expecting WDefInstance, found a WDefInstanceConnector!")) + case _ => s map collectInstances(insts) + } +} diff --git a/src/main/scala/firrtl/analyses/Netlist.scala b/src/main/scala/firrtl/analyses/Netlist.scala deleted file mode 100644 index 99f3645f..00000000 --- a/src/main/scala/firrtl/analyses/Netlist.scala +++ /dev/null @@ -1,97 +0,0 @@ -// See LICENSE for license details. - -package firrtl.analyses - -import scala.collection.mutable - -import firrtl._ -import firrtl.ir._ -import firrtl.graph._ -import firrtl.Utils._ -import firrtl.Mappers._ - - -/** A class representing the instance hierarchy of a working IR Circuit - * - * @constructor constructs an instance graph from a Circuit - * @param c the Circuit to analyze - */ -class InstanceGraph(c: Circuit) { - - private def collectInstances(insts: mutable.Set[WDefInstance]) - (s: Statement): Statement = s match { - case i: WDefInstance => - insts += i - i - case _ => - s map collectInstances(insts) - } - - private val moduleMap = c.modules.map({m => (m.name,m) }).toMap - private val instantiated = new mutable.HashSet[String] - private val childInstances = - new mutable.HashMap[String,mutable.Set[WDefInstance]] - for (m <- c.modules) { - childInstances(m.name) = new mutable.HashSet[WDefInstance] - m map collectInstances(childInstances(m.name)) - instantiated ++= childInstances(m.name).map(i => i.module) - } - - private val uninstantiated = moduleMap.keySet -- instantiated - private val instanceGraph = new MutableDiGraph[WDefInstance] - private val instanceQueue = new mutable.Queue[WDefInstance] - - uninstantiated.foreach({ subTop => - val topInstance = WDefInstance(subTop,subTop) - instanceQueue.enqueue(topInstance) - while (!instanceQueue.isEmpty) { - val current = instanceQueue.dequeue - instanceGraph.addVertex(current) - for (child <- childInstances(current.module)) { - if (!instanceGraph.contains(child)) { - instanceQueue.enqueue(child) - instanceGraph.addVertex(child) - } - instanceGraph.addEdge(current,child) - } - } - }) - - // The true top module (circuit main) - private val trueTopInstance = WDefInstance(c.main, c.main) - - /** A directed graph showing the instance dependencies among modules - * in the circuit. Every WDefInstance of a module has an edge to - * every WDefInstance arising from every instance statement in - * that module. - */ - lazy val graph = DiGraph(instanceGraph) - - /** A list of absolute paths (each represented by a Seq of instances) - * of all module instances in the Circuit. - */ - lazy val fullHierarchy = graph.pathsInDAG(trueTopInstance) - - /** Finds the absolute paths (each represented by a Seq of instances - * representing the chain of hierarchy) of all instances of a - * particular module. - * - * @param module the name of the selected module - * @return a Seq[Seq[WDefInstance]] of absolute instance paths - */ - def findInstancesInHierarchy(module: String): Seq[Seq[WDefInstance]] = { - val instances = graph.getVertices.filter(_.module == module).toSeq - instances flatMap { i => fullHierarchy(i) } - } - - /** An `[[EulerTour]]` representation of the `[[DiGraph]]` */ - lazy val tour = EulerTour(graph, trueTopInstance) - - /** Finds the lowest common ancestor instances for two module names in - * a design - */ - def lowestCommonAncestor(moduleA: Seq[WDefInstance], - moduleB: Seq[WDefInstance]): Seq[WDefInstance] = { - tour.rmq(moduleA, moduleB) - } -} -- cgit v1.2.3