diff options
Diffstat (limited to 'src/main/scala/firrtl/analyses')
| -rw-r--r-- | src/main/scala/firrtl/analyses/CircuitGraph.scala | 11 | ||||
| -rw-r--r-- | src/main/scala/firrtl/analyses/InstanceGraph.scala | 17 | ||||
| -rw-r--r-- | src/main/scala/firrtl/analyses/InstanceKeyGraph.scala | 72 |
3 files changed, 86 insertions, 14 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 |