[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, 94 insertions, 5 deletions

diff --git a/src/main/scala/firrtl/annotations/Target.scala b/src/main/scala/firrtl/annotations/Target.scala
index e7ea07ca..4d1cdc2f 100644
--- a/src/main/scala/firrtl/annotations/Target.scala
+++ b/src/main/scala/firrtl/annotations/Target.scala
@@ -99,6 +99,15 @@ sealed trait Target extends Named {
 
   /** Whether the target is directly instantiated in its root module */
   def isLocal: Boolean
+
+  /** Share root module */
+  def sharedRoot(other: Target): Boolean = this.moduleOpt == other.moduleOpt && other.moduleOpt.nonEmpty
+
+  /** Checks whether this is inside of other */
+  def encapsulatedBy(other: IsModule): Boolean = this.moduleOpt.contains(other.encapsulatingModule)
+
+  /** @return Returns the instance hierarchy path, if one exists */
+  def path: Seq[(Instance, OfModule)]
 }
 
 object Target {
@@ -193,6 +202,33 @@ object Target {
     case b: InstanceTarget  => b.ofModuleTarget
     case b: ReferenceTarget => b.pathlessTarget.moduleTarget
   }
+
+  def getPathlessTarget(t: Target): Target = {
+    t.tryToComplete match {
+      case c: CircuitTarget => c
+      case m: IsMember => m.pathlessTarget
+      case t: GenericTarget if t.isLegal =>
+        val newTokens = t.tokens.dropWhile(x => x.isInstanceOf[Instance] || x.isInstanceOf[OfModule])
+        GenericTarget(t.circuitOpt, t.moduleOpt, newTokens)
+      case other => sys.error(s"Can't make $other pathless!")
+    }
+  }
+
+  def getReferenceTarget(t: Target): Target = {
+    (t.toGenericTarget match {
+      case t: GenericTarget if t.isLegal =>
+        val newTokens = t.tokens.reverse.dropWhile({
+          case x: Field => true
+          case x: Index => true
+          case Clock => true
+          case Init => true
+          case Reset => true
+          case other => false
+        }).reverse
+        GenericTarget(t.circuitOpt, t.moduleOpt, newTokens)
+      case other => sys.error(s"Can't make $other pathless!")
+    }).tryToComplete
+  }
 }
 
 /** Represents incomplete or non-standard [[Target]]s
@@ -235,6 +271,12 @@ case class GenericTarget(circuitOpt: Option[String],
 
   override def isLocal: Boolean = !(getPath.nonEmpty && getPath.get.nonEmpty)
 
+  def path: Vector[(Instance, OfModule)] = if(isComplete){
+    tokens.zip(tokens.tail).collect {
+      case (i: Instance, o: OfModule) => (i, o)
+    }
+  } else Vector.empty[(Instance, OfModule)]
+
   /** If complete, return this [[GenericTarget]]'s path
     * @return
     */
@@ -342,6 +384,14 @@ case class GenericTarget(circuitOpt: Option[String],
   def isCircuitTarget: Boolean = circuitOpt.nonEmpty && moduleOpt.isEmpty && tokens.isEmpty
   def isModuleTarget: Boolean = circuitOpt.nonEmpty && moduleOpt.nonEmpty && tokens.isEmpty
   def isComponentTarget: Boolean = circuitOpt.nonEmpty && moduleOpt.nonEmpty && tokens.nonEmpty
+
+  lazy val (parentModule: Option[String], astModule: Option[String]) = path match {
+    case Seq() => (None, moduleOpt)
+    case Seq((i, OfModule(o))) => (moduleOpt, Some(o))
+    case seq if seq.size > 1 =>
+      val reversed = seq.reverse
+      (Some(reversed(1)._2.value), Some(reversed(0)._2.value))
+  }
 }
 
 /** Concretely points to a FIRRTL target, no generic selectors
@@ -368,7 +418,7 @@ trait CompleteTarget extends Target {
   override def toTarget: CompleteTarget = this
 
   // Very useful for debugging, I (@azidar) think this is reasonable
-  override def toString = serialize
+  override def toString: String = serialize
 }
 
 
@@ -417,6 +467,13 @@ trait IsMember extends CompleteTarget {
     * @return
     */
   def setPathTarget(newPath: IsModule): CompleteTarget
+
+  /** @return The [[ModuleTarget]] of the module that directly contains this component */
+  def encapsulatingModule: String = if(path.isEmpty) module else path.last._2.value
+
+  def encapsulatingModuleTarget: ModuleTarget = ModuleTarget(circuit, encapsulatingModule)
+
+  def leafModule: String
 }
 
 /** References a module-like target (e.g. a [[ModuleTarget]] or an [[InstanceTarget]])
@@ -435,10 +492,6 @@ trait IsModule extends IsMember {
 /** A component of a FIRRTL Module (e.g. cannot point to a CircuitTarget or ModuleTarget)
   */
 trait IsComponent extends IsMember {
-
-  /** @return The [[ModuleTarget]] of the module that directly contains this component */
-  def encapsulatingModule: String = if(path.isEmpty) module else path.last._2.value
-
   /** Removes n levels of instance hierarchy
     *
     * Example: n=1, transforms (Top, A)/b:B/c:C -> (Top, B)/c:C
@@ -505,6 +558,8 @@ case class CircuitTarget(circuit: String) extends CompleteTarget {
   override def addHierarchy(root: String, instance: String): ReferenceTarget =
     ReferenceTarget(circuit, root, Nil, instance, Nil)
 
+  override def path = Seq()
+
   override def toNamed: CircuitName = CircuitName(circuit)
 }
 
@@ -545,6 +600,8 @@ case class ModuleTarget(circuit: String, module: String) extends IsModule {
   override def setPathTarget(newPath: IsModule): IsModule = newPath
 
   override def toNamed: ModuleName = ModuleName(module, CircuitName(circuit))
+
+  override def leafModule: String = module
 }
 
 /** Target pointing to a declared named component in a [[firrtl.ir.DefModule]]
@@ -631,6 +688,30 @@ case class ReferenceTarget(circuit: String,
     ReferenceTarget(newPath.circuit, newPath.module, newPath.asPath, ref, component)
 
   override def asPath: Seq[(Instance, OfModule)] = path
+
+  def isClock: Boolean = tokens.last == Clock
+
+  def isInit: Boolean = tokens.last == Init
+
+  def isReset: Boolean = tokens.last == Reset
+
+  def noComponents: ReferenceTarget = this.copy(component = Nil)
+
+  def leafSubTargets(tpe: firrtl.ir.Type): Seq[ReferenceTarget] = tpe match {
+    case _: firrtl.ir.GroundType => Vector(this)
+    case firrtl.ir.VectorType(t, size) => (0 until size).flatMap { i => index(i).leafSubTargets(t) }
+    case firrtl.ir.BundleType(fields) => fields.flatMap { f => field(f.name).leafSubTargets(f.tpe)}
+    case other => sys.error(s"Error! Unexpected type $other")
+  }
+
+  def allSubTargets(tpe: firrtl.ir.Type): Seq[ReferenceTarget] = tpe match {
+    case _: firrtl.ir.GroundType => Vector(this)
+    case firrtl.ir.VectorType(t, size) => this +: (0 until size).flatMap { i => index(i).allSubTargets(t) }
+    case firrtl.ir.BundleType(fields) => this +: fields.flatMap { f => field(f.name).allSubTargets(f.tpe)}
+    case other => sys.error(s"Error! Unexpected type $other")
+  }
+
+  override def leafModule: String = encapsulatingModule
 }
 
 /** Points to an instance declaration of a module (termed an ofModule)
@@ -652,6 +733,12 @@ case class InstanceTarget(circuit: String,
   /** @return a [[ModuleTarget]] referring to declaration of this ofModule */
   def ofModuleTarget: ModuleTarget = ModuleTarget(circuit, ofModule)
 
+  /** @return a [[ReferenceTarget]] referring to given reference within this instance */
+  def addReference(rt: ReferenceTarget): ReferenceTarget = {
+    require(rt.module == ofModule)
+    ReferenceTarget(circuit, module, asPath, rt.ref, rt.component)
+  }
+
   override def circuitOpt: Option[String] = Some(circuit)
 
   override def moduleOpt: Option[String] = Some(module)
@@ -690,6 +777,8 @@ case class InstanceTarget(circuit: String,
 
   override def setPathTarget(newPath: IsModule): InstanceTarget =
     InstanceTarget(newPath.circuit, newPath.module, newPath.asPath, instance, ofModule)
+
+  override def leafModule: String = ofModule
 }