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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
// SPDX-License-Identifier: Apache-2.0
package firrtlTests.analyses
import firrtl.annotations.TargetToken.OfModule
import firrtl.analyses.InstanceGraph
import firrtl.graph.DiGraph
import firrtl.WDefInstance
import firrtl.passes._
import firrtl.testutils._
class InstanceGraphTests extends FirrtlFlatSpec {
private def getEdgeSet(graph: DiGraph[String]): collection.Map[String, collection.Set[String]] = {
(graph.getVertices.map { v => (v, graph.getEdges(v)) }).toMap
}
behavior.of("InstanceGraph")
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
"""
val circuit = ToWorkingIR.run(parse(input))
val graph = new InstanceGraph(circuit).graph.transformNodes(_.module)
getEdgeSet(graph) shouldBe Map(
"Top" -> Set("Child1", "Child2"),
"Child1" -> Set("Child1a", "Child1b"),
"Child2" -> Set(),
"Child1a" -> Set(),
"Child1b" -> Set()
)
}
it should "find hierarchical instances correctly in 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
"""
val circuit = ToWorkingIR.run(parse(input))
val iGraph = new InstanceGraph(circuit)
iGraph.findInstancesInHierarchy("Top") shouldBe Seq(Seq(WDefInstance("Top", "Top")))
iGraph.findInstancesInHierarchy("Child1") shouldBe Seq(Seq(WDefInstance("Top", "Top"), WDefInstance("c", "Child1")))
iGraph.findInstancesInHierarchy("Top2") shouldBe Nil
iGraph.findInstancesInHierarchy("Child2") shouldBe Nil
iGraph.findInstancesInHierarchy("Child2a") shouldBe Nil
iGraph.findInstancesInHierarchy("Child2b") shouldBe Nil
iGraph.findInstancesInHierarchy("Child3") shouldBe Nil
}
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
"""
val circuit = ToWorkingIR.run(parse(input))
val graph = new InstanceGraph(circuit).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
"""
val circuit = ToWorkingIR.run(parse(input))
val graph = (new InstanceGraph(circuit)).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")
}
// Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
// experience non-determinism
it should "preserve Module declaration order" 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 circuit = ToWorkingIR.run(parse(input))
val instGraph = new InstanceGraph(circuit)
val childMap = instGraph.getChildrenInstances
childMap.keys.toSeq should equal(Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
}
// Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
// experience non-determinism
it should "preserve Instance declaration 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
| inst f of Child
| module Child :
| skip
|""".stripMargin
val circuit = ToWorkingIR.run(parse(input))
val instGraph = new InstanceGraph(circuit)
val childMap = instGraph.getChildrenInstances
val insts = childMap("Top").toSeq.map(_.name)
insts should equal(Seq("a", "b", "c", "d", "e", "f"))
}
// 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 circuit = ToWorkingIR.run(parse(input))
val instGraph = new InstanceGraph(circuit)
val hier = instGraph.fullHierarchy
hier.keys.toSeq.map(_.name) should equal(Seq("Top", "a", "b", "c", "d", "e"))
}
behavior.of("InstanceGraph.staticInstanceCount")
it should "report that there is one instance of the top module" in {
val input =
"""|circuit Foo:
| module Foo:
| skip
|""".stripMargin
val iGraph = new InstanceGraph(ToWorkingIR.run(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 = new InstanceGraph(ToWorkingIR.run(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 = new InstanceGraph(ToWorkingIR.run(parse(input)))
val expectedCounts = Map(OfModule("Foo") -> 1, OfModule("Bar") -> 0)
iGraph.staticInstanceCount should be(expectedCounts)
}
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 = new InstanceGraph(ToWorkingIR.run(parse(input)))
iGraph.modules should contain theSameElementsAs Seq(OfModule("Top"), OfModule("Reachable"), OfModule("Unreachable"))
iGraph.reachableModules should contain theSameElementsAs Seq(OfModule("Top"), OfModule("Reachable"))
iGraph.unreachableModules should contain theSameElementsAs Seq(OfModule("Unreachable"))
}
}
|
