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
|
// 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.traversals.Foreachers._
import firrtl.annotations.TargetToken.{Instance, OfModule}
/** 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) {
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[WDefInstance]]
for (m <- c.modules) {
childInstances(m.name) = new mutable.LinkedHashSet[WDefInstance]
m.foreach(InstanceGraph.collectInstances(childInstances(m.name)))
instantiated ++= childInstances(m.name).map(i => i.module)
}
private val instanceGraph = new MutableDiGraph[WDefInstance]
private val instanceQueue = new mutable.Queue[WDefInstance]
for (subTop <- c.modules.view.map(_.name).filterNot(instantiated)) {
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: mutable.LinkedHashMap[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]] = {
if (instantiated(module)) {
val instances = graph.getVertices.filter(_.module == module).toSeq
instances flatMap { i => fullHierarchy(i) }
} else {
Nil
}
}
/** An [[firrtl.graph.EulerTour EulerTour]] representation of the [[firrtl.graph.DiGraph 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(_))
}
/** Given a circuit, returns a map from module name to children
* instance/module definitions
*/
def getChildrenInstances: mutable.LinkedHashMap[String, mutable.LinkedHashSet[WDefInstance]] = childInstances
/** Given a circuit, returns a map from module name to children
* instance/module [[firrtl.annotations.TargetToken]]s
*/
def getChildrenInstanceOfModule: mutable.LinkedHashMap[String, mutable.LinkedHashSet[(Instance, OfModule)]] =
childInstances.map(kv => kv._1 -> kv._2.map(i => (Instance(i.name), OfModule(i.module))))
}
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): Unit = s match {
case i: WDefInstance => insts += i
case i: DefInstance => throwInternalError("Expecting WDefInstance, found a DefInstance!")
case i: WDefInstanceConnector => throwInternalError("Expecting WDefInstance, found a WDefInstanceConnector!")
case _ => s.foreach(collectInstances(insts))
}
}
|
