From f22652a330afe1daa77be2aadb525d65ab05e9fe Mon Sep 17 00:00:00 2001 From: Jiuyang Liu Date: Sat, 1 Aug 2020 00:25:13 +0800 Subject: [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 Co-authored-by: Albert Magyar Co-authored-by: Jack Koenig --- src/main/scala/firrtl/graph/DiGraph.scala | 21 ++++++++++----------- 1 file changed, 10 insertions(+), 11 deletions(-) (limited to 'src/main/scala/firrtl/graph') 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)) -- cgit v1.2.3