[WIP] Implement CircuitGraph and IRLookup to firrtl.analyses (#1603)

* WIP Commit

* Add EdgeDataDiGraph with views to amortize graph construction

* WIP, got basic structure, need tests to pipeclean

* First tests pass. Need more.

* Tests pass, more need to be written

* More tests pass! Things should work, except for memories

* Added clearPrev to fix digraph uses where caching prev breaks

* Removed old Component. Documented IRLookup

* Added comments. Make prev arg to getEdges

* WIP: Refactoring for CircuitGraph

* Refactored into CircuitGraph. Can do topological module analysis

* Removed old versions

* Added support for memories

* Added cached test

* More stufffff

* Added implicit caching of connectivity

* Added tests for IRLookup, and others

* Many major changes.

Replaced CircuitGraph as ConnectionGraph
Added CircuitGraph to be top-level user-facing object
ConnectionGraph now automatically shortcuts getEdges
ConnectionGraph overwrites BFS as PriorityBFS
Added leafModule to Target
Added lookup by kind to IRLookup
Added more tests

* Reordered stuff in ConnectionGraph

* Made path work with deep hierarchies. Added PML for IllegalClockCrossings

* Made pathsInDAG work with current shortcut semantics

* Bugfix: check pathless targets when shortcutting paths

* Added documentation/licenses

* Removed UnnamedToken and related functionality

* Added documentation of ConnectionGraph

* Added back topo, needed for correct solving of intermediate modules

* Bugfix. Cache intermediate clockSources from same BFS with same root, but not BFS with different root

* Added literal/invalid clock source, and unknown top for getclocksource

* Bugfix for clocks in bundles

* Add CompleteTargetSerializer and test

* remove ClockFinder, be able to compile.

* test is able to compile, but need to fix.

* public and abstract DiGraph, remove DiGraphLike.

* revert some DiGraph code, ConnectionGraphSpec passed.

* CircuitGraphSpec passed.

* minimize diff between master

* codes clean up

* override linearize and revert DiGraph

* keep DiGraph unchanged.

* make ci happy again.

* codes clean up.

* bug fix for rebase

* remove wir

* make scaladoc happy again.

* update for review.

* add some documentation.

* remove tag

* wip IRLookup

* code clean up and add some doucmentations.

* IRLookup cache with ModuleTarget guarded.

* make unidoc and 2.13 happy

Co-authored-by: Adam Izraelevitz <azidar@gmail.com>
Co-authored-by: Albert Magyar <albert.magyar@gmail.com>
Co-authored-by: Jack Koenig <koenig@sifive.com>

1 files changed, 10 insertions, 11 deletions

diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala
index f30beec1..32bcac5f 100644
--- a/src/main/scala/firrtl/graph/DiGraph.scala
+++ b/src/main/scala/firrtl/graph/DiGraph.scala
@@ -2,9 +2,8 @@
 
 package firrtl.graph
 
-import scala.collection.{Set, Map}
-import scala.collection.mutable
-import scala.collection.mutable.{LinkedHashSet, LinkedHashMap}
+import scala.collection.{Map, Set, mutable}
+import scala.collection.mutable.{LinkedHashMap, LinkedHashSet}
 
 /** An exception that is raised when an assumed DAG has a cycle */
 class CyclicException(val node: Any) extends Exception(s"No valid linearization for cyclic graph, found at $node")
@@ -18,7 +17,7 @@ object DiGraph {
   def apply[T](mdg: MutableDiGraph[T]): DiGraph[T] = mdg
 
   /** Create a DiGraph from a Map[T,Set[T]] of edge data */
-  def apply[T](edgeData: Map[T,Set[T]]): DiGraph[T] = {
+  def apply[T](edgeData: Map[T, Set[T]]): DiGraph[T] = {
     val edgeDataCopy = new LinkedHashMap[T, LinkedHashSet[T]]
     for ((k, v) <- edgeData) {
       edgeDataCopy(k) = new LinkedHashSet[T]
@@ -34,7 +33,7 @@ object DiGraph {
 }
 
 /** Represents common behavior of all directed graphs */
-class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, LinkedHashSet[T]]) {
+class DiGraph[T] (private[graph] val edges: LinkedHashMap[T, LinkedHashSet[T]]) {
   /** Check whether the graph contains vertex v */
   def contains(v: T): Boolean = edges.contains(v)
 
@@ -188,7 +187,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     *
     * @param start the start node
     * @param end the destination node
-    * @throws PathNotFoundException
+    * @throws firrtl.graph.PathNotFoundException
     * @return a Seq[T] of nodes defining an arbitrary valid path
     */
   def path(start: T, end: T): Seq[T] = path(start, end, Set.empty[T])
@@ -198,7 +197,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * @param start the start node
     * @param end the destination node
     * @param blacklist list of nodes which break path, if encountered
-    * @throws PathNotFoundException
+    * @throws firrtl.graph.PathNotFoundException
     * @return a Seq[T] of nodes defining an arbitrary valid path
     */
   def path(start: T, end: T, blacklist: Set[T]): Seq[T] = {
@@ -336,7 +335,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * Any edge including a deleted node will be deleted
     *
     * @param vprime the Set[T] of desired vertices
-    * @throws scala.IllegalArgumentException if vprime is not a subset of V
+    * @throws java.lang.IllegalArgumentException if vprime is not a subset of V
     * @return the subgraph
     */
   def subgraph(vprime: Set[T]): DiGraph[T] = {
@@ -350,12 +349,12 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * transformed into an edge (u,v).
     *
     * @param vprime the Set[T] of desired vertices
-    * @throws scala.IllegalArgumentException if vprime is not a subset of V
+    * @throws java.lang.IllegalArgumentException if vprime is not a subset of V
     * @return the simplified graph
     */
   def simplify(vprime: Set[T]): DiGraph[T] = {
     require(vprime.subsetOf(edges.keySet))
-    val pathEdges = vprime.map( v => (v, reachableFrom(v) & (vprime-v)) )
+    val pathEdges = vprime.map(v => (v, reachableFrom(v) & (vprime-v)) )
     new DiGraph(new LinkedHashMap[T, LinkedHashSet[T]] ++ pathEdges)
   }
 
@@ -394,7 +393,7 @@ class MutableDiGraph[T] extends DiGraph[T](new LinkedHashMap[T, LinkedHashSet[T]
   }
 
   /** Add edge (u,v) to the graph.
-    * @throws scala.IllegalArgumentException if u and/or v is not in the graph
+    * @throws java.lang.IllegalArgumentException if u and/or v is not in the graph
     */
   def addEdge(u: T, v: T): Unit = {
     require(contains(u))