diff options
Diffstat (limited to 'src/main/scala/firrtl/passes')
| -rw-r--r-- | src/main/scala/firrtl/passes/Inline.scala | 8 | ||||
| -rw-r--r-- | src/main/scala/firrtl/passes/wiring/Wiring.scala | 32 | ||||
| -rw-r--r-- | src/main/scala/firrtl/passes/wiring/WiringUtils.scala | 82 |
3 files changed, 93 insertions, 29 deletions
diff --git a/src/main/scala/firrtl/passes/Inline.scala b/src/main/scala/firrtl/passes/Inline.scala index 39cb4b9c..ad963b19 100644 --- a/src/main/scala/firrtl/passes/Inline.scala +++ b/src/main/scala/firrtl/passes/Inline.scala @@ -7,7 +7,7 @@ import firrtl.ir._ import firrtl.Mappers._ import firrtl.annotations._ import firrtl.annotations.TargetToken.{Instance, OfModule} -import firrtl.analyses.{InstanceGraph} +import firrtl.analyses.InstanceKeyGraph import firrtl.graph.{DiGraph, MutableDiGraph} import firrtl.stage.{Forms, RunFirrtlTransformAnnotation} import firrtl.options.{RegisteredTransform, ShellOption} @@ -80,7 +80,7 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe // 3) All annotated instances exist, and their modules can be inline def check(c: Circuit, moduleNames: Set[ModuleName], instanceNames: Set[ComponentName]): Unit = { val errors = mutable.ArrayBuffer[PassException]() - val moduleMap = new InstanceGraph(c).moduleMap + val moduleMap = InstanceKeyGraph(c).moduleMap def checkExists(name: String): Unit = if (!moduleMap.contains(name)) errors += new PassException(s"Annotated module does not exist: $name") @@ -136,10 +136,10 @@ class InlineInstances extends Transform with DependencyAPIMigration with Registe check(c, modsToInline, instsToInline) val flatModules = modsToInline.map(m => m.name) val flatInstances: Set[(OfModule, Instance)] = instsToInline.map(i => OfModule(i.module.name) -> Instance(i.name)) ++ getInstancesOf(c, flatModules) - val iGraph = new InstanceGraph(c) + val iGraph = InstanceKeyGraph(c) val namespaceMap = collection.mutable.Map[String, Namespace]() // Map of Module name to Map of instance name to Module name - val instMaps = iGraph.getChildrenInstanceMap + val instMaps = iGraph.getChildInstanceMap /** Add a prefix to all declarations updating a [[Namespace]] and appending to a [[RenameMap]] */ def appendNamePrefix( diff --git a/src/main/scala/firrtl/passes/wiring/Wiring.scala b/src/main/scala/firrtl/passes/wiring/Wiring.scala index c62a565e..3f74e5d2 100644 --- a/src/main/scala/firrtl/passes/wiring/Wiring.scala +++ b/src/main/scala/firrtl/passes/wiring/Wiring.scala @@ -5,11 +5,14 @@ package wiring import firrtl._ import firrtl.ir._ + import scala.collection.mutable import firrtl.annotations._ import firrtl.annotations.AnnotationUtils._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.InstanceKeyGraph import WiringUtils._ +import firrtl.analyses.InstanceKeyGraph.InstanceKey +import firrtl.graph.EulerTour /** A data store of one sink--source wiring relationship */ case class WiringInfo(source: ComponentName, sinks: Seq[Named], pin: String) @@ -47,7 +50,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { else ns.newName(tokenize(c) filterNot ("[]." contains _) mkString "_") })}} - val iGraph = new InstanceGraph(c) + val iGraph = InstanceKeyGraph(c) names.zip(portNames).map{ case(WiringNames(comp, so, si, _), pn) => computeModifications(c, iGraph, comp, so, si, pn) } } @@ -67,7 +70,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { * to pending modifications */ private def computeModifications(c: Circuit, - iGraph: InstanceGraph, + iGraph: InstanceKeyGraph, compName: String, source: String, sinks: Seq[Named], @@ -94,12 +97,17 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { def makeWireC(m: Modifications, portName: String, c: (String, String)): Modifications = m.copy(addPortOrWire = Some(m.addPortOrWire.getOrElse((portName, DecWire))), cons = (m.cons :+ c).distinct ) + val tour = EulerTour(iGraph.graph, iGraph.top) + // Finds the lowest common ancestor instances for two module names in a design + def lowestCommonAncestor(moduleA: Seq[InstanceKey], moduleB: Seq[InstanceKey]): Seq[InstanceKey] = + tour.rmq(moduleA, moduleB) + owners.foreach { case (sink, source) => - val lca = iGraph.lowestCommonAncestor(sink, source) + val lca = lowestCommonAncestor(sink, source) // Compute metadata along Sink to LCA paths. sink.drop(lca.size - 1).sliding(2).toList.reverse.foreach { - case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) => + case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) => val to = s"$ci.${portNames(cm)}" val from = s"${portNames(pm)}" meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from)) @@ -107,12 +115,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { addPortOrWire = Some((portNames(cm), DecInput)) ) // Case where the sink is the LCA - case Seq(WDefInstance(_,_,pm,_)) => + case Seq(InstanceKey(_,pm)) => // Case where the source is also the LCA if (source.drop(lca.size).isEmpty) { meta(pm) = makeWire(meta(pm), portNames(pm)) } else { - val WDefInstance(_,ci,cm,_) = source.drop(lca.size).head + val InstanceKey(ci,cm) = source.drop(lca.size).head val to = s"${portNames(pm)}" val from = s"$ci.${portNames(cm)}" meta(pm) = makeWireC(meta(pm), portNames(pm), (to, from)) @@ -120,7 +128,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { } // Compute metadata for the Sink - sink.last match { case WDefInstance(_, _, m, _) => + sink.last match { case InstanceKey( _, m) => if (sinkComponents.contains(m)) { val from = s"${portNames(m)}" sinkComponents(m).foreach( to => @@ -132,7 +140,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { } // Compute metadata for the Source - source.last match { case WDefInstance(_, _, m, _) => + source.last match { case InstanceKey( _, m) => val to = s"${portNames(m)}" val from = compName meta(m) = meta(m).copy( @@ -142,7 +150,7 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { // Compute metadata along Source to LCA path source.drop(lca.size - 1).sliding(2).toList.reverse.map { - case Seq(WDefInstance(_,_,pm,_), WDefInstance(_,ci,cm,_)) => { + case Seq(InstanceKey(_,pm), InstanceKey(ci,cm)) => { val to = s"${portNames(pm)}" val from = s"$ci.${portNames(cm)}" meta(pm) = meta(pm).copy( @@ -153,12 +161,12 @@ class Wiring(wiSeq: Seq[WiringInfo]) extends Pass { ) } // Case where the source is the LCA - case Seq(WDefInstance(_,_,pm,_)) => { + case Seq(InstanceKey(_,pm)) => { // Case where the sink is also the LCA. We do nothing here, // as we've created the connecting wire above if (sink.drop(lca.size).isEmpty) { } else { - val WDefInstance(_,ci,cm,_) = sink.drop(lca.size).head + val InstanceKey(ci,cm) = sink.drop(lca.size).head val to = s"$ci.${portNames(cm)}" val from = s"${portNames(pm)}" meta(pm) = meta(pm).copy( diff --git a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala index 5f09bbe0..c220692a 100644 --- a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala +++ b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala @@ -7,11 +7,13 @@ import firrtl._ import firrtl.ir._ import firrtl.Utils._ import firrtl.Mappers._ +import firrtl.analyses.InstanceKeyGraph.InstanceKey import firrtl.traversals.Foreachers._ + import scala.collection.mutable import firrtl.annotations._ import firrtl.annotations.AnnotationUtils._ -import firrtl.analyses.InstanceGraph +import firrtl.analyses.{InstanceGraph, InstanceKeyGraph} /** Declaration kind in lineage (e.g. input port, output port, wire) */ @@ -112,9 +114,66 @@ object WiringUtils { * @return a map of sink instance names to source instance names * @throws WiringException if a sink is equidistant to two sources */ - @deprecated("This method can lead to non-determinism in your compiler pass. Use sinksToSourcesSeq instead!", "Firrtl 1.4") - def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] = - sinksToSourcesSeq(sinks, source, i).toMap + @deprecated("This method can lead to non-determinism in your compiler pass and exposes internal details." + + " Please file an issue with firrtl if you have a use case!", "Firrtl 1.4") + def sinksToSources(sinks: Seq[Named], source: String, i: InstanceGraph): Map[Seq[WDefInstance], Seq[WDefInstance]] = { + // The order of owners influences the order of the results, it thus needs to be deterministic with a LinkedHashMap. + val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]] + val queue = new mutable.Queue[Seq[WDefInstance]] + val visited = new mutable.HashMap[Seq[WDefInstance], Boolean].withDefaultValue(false) + + val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source => v } + sourcePaths.flatten.foreach { l => + queue.enqueue(l) + owners(l) = Vector(l) + } + + val sinkModuleNames = sinks.map(getModuleName).toSet + val sinkPaths = i.fullHierarchy.collect { case (k,v) if sinkModuleNames.contains(k.module) => v } + // sinkInsts needs to have unique entries but is also iterated over which is why we use a LinkedHashSet + val sinkInsts = mutable.LinkedHashSet() ++ sinkPaths.flatten + + /** If we're lucky and there is only one source, then that source owns + * all sinks. If we're unlucky, we need to do a full (slow) BFS + * to figure out who owns what. Currently, the BFS is not + * performant. + * + * [todo] The performance of this will need to be improved. + * Possible directions are that if we're purely source-under-sink + * or sink-under-source, then ownership is trivially a mapping + * down/up. Ownership seems to require a BFS if we have + * sources/sinks not under sinks/sources. + */ + if (queue.size == 1) { + val u = queue.dequeue + sinkInsts.foreach { v => owners(v) = Vector(u) } + } else { + while (queue.nonEmpty) { + val u = queue.dequeue + visited(u) = true + + val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1)) + + // [todo] This is the critical section + edges + .filter( e => !visited(e) && e.nonEmpty ) + .foreach{ v => + owners(v) = owners.getOrElse(v, Vector()) ++ owners(u) + queue.enqueue(v) + } + } + + // Check that every sink has one unique owner. The only time that + // this should fail is if a sink is equidistant to two sources. + sinkInsts.foreach { s => + if (!owners.contains(s) || owners(s).size > 1) { + throw new WiringException( + s"Unable to determine source mapping for sink '${s.map(_.name)}'") } + } + } + + owners.collect { case (k, v) if sinkInsts.contains(k) => (k, v.flatten) }.toMap + } /** Return a map of sink instances to source instances that minimizes * distance @@ -125,15 +184,12 @@ object WiringUtils { * @return a map of sink instance names to source instance names * @throws WiringException if a sink is equidistant to two sources */ - def sinksToSourcesSeq(sinks: Seq[Named], - source: String, - i: InstanceGraph): - Seq[(Seq[WDefInstance], Seq[WDefInstance])] = { + private[firrtl] def sinksToSourcesSeq(sinks: Seq[Named], source: String, i: InstanceKeyGraph): + Seq[(Seq[InstanceKey], Seq[InstanceKey])] = { // The order of owners influences the order of the results, it thus needs to be deterministic with a LinkedHashMap. - val owners = new mutable.LinkedHashMap[Seq[WDefInstance], Vector[Seq[WDefInstance]]] - val queue = new mutable.Queue[Seq[WDefInstance]] - val visited = new mutable.HashMap[Seq[WDefInstance], Boolean] - .withDefaultValue(false) + val owners = new mutable.LinkedHashMap[Seq[InstanceKey], Vector[Seq[InstanceKey]]] + val queue = new mutable.Queue[Seq[InstanceKey]] + val visited = new mutable.HashMap[Seq[InstanceKey], Boolean].withDefaultValue(false) val sourcePaths = i.fullHierarchy.collect { case (k,v) if k.module == source => v } sourcePaths.flatten.foreach { l => @@ -165,7 +221,7 @@ object WiringUtils { val u = queue.dequeue visited(u) = true - val edges = (i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1)) + val edges = i.graph.getEdges(u.last).map(u :+ _).toVector :+ u.dropRight(1) // [todo] This is the critical section edges |