1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
// SPDX-License-Identifier: Apache-2.0
package firrtl.analyses
import scala.collection.mutable
import firrtl._
import firrtl.ir._
import firrtl.graph._
import firrtl.Utils._
import firrtl.traversals.Foreachers._
import firrtl.annotations.TargetToken._
/** 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
* @note The current implementation has some performance problems, which is why [[InstanceKeyGraph]]
* exists and should be preferred for new use cases. Eventually the old class will be deprecated
* in favor of the new implementation.
* The performance problems in the old implementation stem from the fact that DefInstance is used as the
* key to the underlying Map. DefInstance contains the type of the module besides the module and instance names.
* This type is not needed as it can be inferred from the module name. If the module name is the same,
* the type will be the same and vice versa.
* 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 =
new mutable.LinkedHashMap[String, mutable.LinkedHashSet[DefInstance]]
for (m <- c.modules) {
childInstances(m.name) = new mutable.LinkedHashSet[DefInstance]
m.foreach(InstanceGraph.collectInstances(childInstances(m.name)))
instantiated ++= childInstances(m.name).map(i => i.module)
}
private val instanceGraph = new MutableDiGraph[DefInstance]
private val instanceQueue = new mutable.Queue[DefInstance]
for (subTop <- c.modules.view.map(_.name).filterNot(instantiated)) {
val topInstance = DefInstance(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 = DefInstance(c.main, c.main)
/** A directed graph showing the instance dependencies among modules
* in the circuit. Every DefInstance of a module has an edge to
* 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
* 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.
*/
@deprecated("Use InstanceKeyGraph.staticInstanceCount instead.", "FIRRTL 1.4")
lazy val staticInstanceCount: Map[OfModule, Int] = {
val foo = mutable.LinkedHashMap.empty[OfModule, Int]
childInstances.keys.foreach {
case main if main == c.main => foo += main.OfModule -> 1
case other => foo += other.OfModule -> 0
}
childInstances.values.flatten.map(_.OfModule).foreach {
case 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)
* module of the circuit. If the module is not instantiated within the
* hierarchy of the top module of the circuit, it will return Nil.
*
* @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)
}
/**
* 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(_))
}
/** 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))
// Transforms a TraversableOnce input into an order-preserving map
// Iterates only once, no intermediate collections
// Can possibly be replaced using LinkedHashMap.from(..) or better immutable map in Scala 2.13
private def asOrderedMap[K1, K2, V](it: TraversableOnce[K1], f: (K1) => (K2, V)): collection.Map[K2, V] = {
val lhmap = new mutable.LinkedHashMap[K2, V]
it.foreach { lhmap += f(_) }
lhmap
}
/** 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
*
* @param insts mutable datastructure to append to
* @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
case i: WDefInstanceConnector => throwInternalError("Expecting DefInstance, found a DefInstanceConnector!")
case _ => s.foreach(collectInstances(insts))
}
}
|
