Clock List Transform (#365)

Added clocklist transform

8 files changed, 356 insertions, 0 deletions

diff --git a/src/main/scala/firrtl/ExecutionOptionsManager.scala b/src/main/scala/firrtl/ExecutionOptionsManager.scala
index ae0636d9..704992c2 100644
--- a/src/main/scala/firrtl/ExecutionOptionsManager.scala
+++ b/src/main/scala/firrtl/ExecutionOptionsManager.scala
@@ -5,6 +5,7 @@ package firrtl
 import firrtl.Annotations._
 import firrtl.Parser._
 import firrtl.passes.memlib.{InferReadWriteAnnotation, ReplSeqMemAnnotation}
+import firrtl.passes.clocklist.ClockListAnnotation
 import logger.LogLevel
 import scopt.OptionParser
 
@@ -291,6 +292,19 @@ trait HasFirrtlOptions {
       "Replace sequential memories with blackboxes + configuration file"
     }
 
+  parser.opt[String]("list-clocks")
+    .abbr("clks")
+    .valueName ("-c:<circuit>:-m:<module>:-o:<filename>")
+    .foreach { x =>
+      firrtlOptions = firrtlOptions.copy(
+        annotations = firrtlOptions.annotations :+ ClockListAnnotation(x),
+        customTransforms = firrtlOptions.customTransforms :+ new passes.clocklist.ClockListTransform
+      )
+    }
+    .text {
+      "List which signal drives each clock of every descendent of specified module"
+    }
+
   parser.note("")
 
 }
diff --git a/src/main/scala/firrtl/passes/clocklist/ClockList.scala b/src/main/scala/firrtl/passes/clocklist/ClockList.scala
new file mode 100644
index 00000000..d0920406
--- /dev/null
+++ b/src/main/scala/firrtl/passes/clocklist/ClockList.scala
@@ -0,0 +1,72 @@
+// See license file for details
+
+package firrtl.passes
+package clocklist
+
+import firrtl._
+import firrtl.ir._
+import Annotations._
+import Utils.error
+import java.io.{File, CharArrayWriter, PrintWriter, Writer}
+import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
+import wiring.Lineage
+import ClockListUtils._
+import Utils._
+import memlib.AnalysisUtils._
+import memlib._
+import Mappers._
+
+/** Starting with a top module, determine the clock origins of each child instance.
+ *  Write the result to writer.
+ */
+class ClockList(top: String, writer: Writer) extends Pass {
+  def name = this.getClass.getSimpleName
+  def run(c: Circuit): Circuit = {
+    // Build useful datastructures
+    val childrenMap = getChildrenMap(c)
+    val moduleMap = c.modules.foldLeft(Map[String, DefModule]())((map, m) => map + (m.name -> m))
+    val lineages = getLineage(childrenMap, top)
+    val outputBuffer = new CharArrayWriter
+
+    // === Checks ===
+    // TODO(izraelevitz): Check all registers/memories use "clock" clock port
+    // ==============
+    
+    // Clock sources must be blackbox outputs and top's clock
+    val partialSourceList = getSourceList(moduleMap)(lineages)
+    val sourceList = partialSourceList ++ moduleMap(top).ports.collect{ case Port(i, n, Input, ClockType) => n }
+    writer.append(s"Sourcelist: $sourceList \n")
+
+    // Remove everything from the circuit, unless it has a clock type
+    // This simplifies the circuit drastically so InlineInstances doesn't take forever.
+    val onlyClockCircuit = RemoveAllButClocks.run(c)
+    
+    // Inline the clock-only circuit up to the specified top module
+    val modulesToInline = (c.modules.collect { case Module(_, n, _, _) if n != top => ModuleName(n, CircuitName(c.main)) }).toSet
+    val inlineTransform = new InlineInstances
+    val inlinedCircuit = inlineTransform.run(onlyClockCircuit, modulesToInline, Set()).circuit
+    val topModule = inlinedCircuit.modules.find(_.name == top).getOrElse(throwInternalError)
+
+    // Build a hashmap of connections to use for getOrigins
+    val connects = getConnects(topModule)
+
+    // Return a map from instance name to clock origin
+    val origins = getOrigins(connects, "", moduleMap)(lineages)
+
+    // If the clock origin is contained in the source list, label good (otherwise bad)
+    origins.foreach { case (instance, origin) =>
+      val sep = if(instance == "") "" else "."
+      if(!sourceList.contains(origin.replace('.','$'))){
+        outputBuffer.append(s"Bad Origin of $instance${sep}clock is $origin\n")
+      } else {
+        outputBuffer.append(s"Good Origin of $instance${sep}clock is $origin\n")
+      }
+    }
+
+    // Write to output file
+    writer.write(outputBuffer.toString)
+
+    // Return unchanged circuit
+    c
+  }
+}
diff --git a/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala b/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala
new file mode 100644
index 00000000..b901e4e8
--- /dev/null
+++ b/src/main/scala/firrtl/passes/clocklist/ClockListTransform.scala
@@ -0,0 +1,76 @@
+// See license file for details
+
+package firrtl.passes
+package clocklist
+
+import firrtl._
+import firrtl.ir._
+import Annotations._
+import Utils.error
+import java.io.{File, CharArrayWriter, PrintWriter, Writer}
+import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
+import wiring.Lineage
+import ClockListUtils._
+import Utils._
+import memlib.AnalysisUtils._
+import memlib._
+import Mappers._
+
+case class ClockListAnnotation(target: ModuleName, outputConfig: String)
+    extends Annotation with Loose with Unstable {
+  def transform = classOf[ClockListTransform]
+  def duplicate(n: Named) = n match {
+    case m: ModuleName => this.copy(target = m, outputConfig = outputConfig)
+    case _ => error("Clocklist can only annotate a module.")
+  }
+}
+
+object ClockListAnnotation {
+  def apply(t: String) = {
+    val usage = """
+[Optional] ClockList
+  List which signal drives each clock of every descendent of specified module
+
+Usage: 
+  --list-clocks -c:<circuit>:-m:<module>:-o:<filename>
+  *** Note: sub-arguments to --list-clocks should be delimited by : and not white space!
+"""    
+  
+    //Parse pass options
+    val passOptions = PassConfigUtil.getPassOptions(t, usage)
+    val outputConfig = passOptions.getOrElse(
+      OutputConfigFileName, 
+      error("No output config file provided for ClockList!" + usage)
+    )
+    val passCircuit = passOptions.getOrElse(
+      PassCircuitName, 
+      error("No circuit name specified for ClockList!" + usage)
+    )
+    val passModule = passOptions.getOrElse(
+      PassModuleName, 
+      error("No module name specified for ClockList!" + usage)
+    )
+    passOptions.get(InputConfigFileName) match {
+      case Some(x) => error("Unneeded input config file name!" + usage)
+      case None =>
+    }
+    val target = ModuleName(passModule, CircuitName(passCircuit))
+    new ClockListAnnotation(target, outputConfig)
+  }
+}
+
+class ClockListTransform extends Transform {
+  def inputForm = LowForm
+  def outputForm = LowForm
+  def passSeq(top: String, writer: Writer): Seq[Pass] =
+    Seq(new ClockList(top, writer))
+  def execute(state: CircuitState): CircuitState = getMyAnnotations(state) match {
+    case Seq(ClockListAnnotation(ModuleName(top, CircuitName(state.circuit.main)), out)) => 
+      val outputFile = new PrintWriter(out)
+      val newC = (new ClockList(top, outputFile)).run(state.circuit)
+      outputFile.close()
+      CircuitState(newC, state.form)
+    case Nil => CircuitState(state.circuit, state.form)
+    case seq => error(s"Found illegal clock list annotation(s): $seq")
+  }
+}
diff --git a/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala b/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala
new file mode 100644
index 00000000..c79b6d1a
--- /dev/null
+++ b/src/main/scala/firrtl/passes/clocklist/ClockListUtils.scala
@@ -0,0 +1,62 @@
+// See license file for details
+
+package firrtl.passes
+package clocklist
+
+import firrtl._
+import firrtl.ir._
+import Annotations._
+import Utils.error
+import java.io.{File, CharArrayWriter, PrintWriter, Writer}
+import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
+import wiring.Lineage
+import ClockListUtils._
+import Utils._
+import memlib.AnalysisUtils._
+import memlib._
+import Mappers._
+
+object ClockListUtils {
+  /** Returns a list of clock outputs from instances of external modules
+   */
+  def getSourceList(moduleMap: Map[String, DefModule])(lin: Lineage): Seq[String] = {
+    val s = lin.foldLeft(Seq[String]()){case (sL, (i, l)) =>
+      val sLx = getSourceList(moduleMap)(l)
+      val sLxx = sLx map (i + "$" + _)
+      sL ++ sLxx
+    }
+    val sourceList = moduleMap(lin.name) match {
+      case ExtModule(i, n, ports, dn, p) =>
+        val portExps = ports.flatMap{p => create_exps(WRef(p.name, p.tpe, PortKind, to_gender(p.direction)))}
+        portExps.filter(e => (e.tpe == ClockType) && (gender(e) == FEMALE)).map(_.serialize)
+      case _ => Nil
+    }
+    val sx = sourceList ++ s
+    sx
+  }
+  /** Returns a map from instance name to its clock origin.
+   *  Child instances are not included if they share the same clock as their parent
+   */
+  def getOrigins(connects: Connects, me: String, moduleMap: Map[String, DefModule])(lin: Lineage): Map[String, String] = {
+    val sep = if(me == "") "" else "$"
+    // Get origins from all children
+    val childrenOrigins = lin.foldLeft(Map[String, String]()){case (o, (i, l)) =>
+      o ++ getOrigins(connects, me + sep + i, moduleMap)(l)
+    }
+    // If I have a clock, get it
+    val clockOpt = moduleMap(lin.name) match {
+      case Module(i, n, ports, b) => ports.collectFirst { case p if p.name == "clock" => me + sep + "clock" }
+      case ExtModule(i, n, ports, dn, p) => None
+    }
+    // Return new origins with children removed, if they match my clock
+    clockOpt match {
+      case Some(clock) =>
+        val myOrigin = getOrigin(connects, clock).serialize
+        childrenOrigins.foldLeft(Map(me -> myOrigin)) { case (o, (childInstance, childOrigin)) =>
+          if(childOrigin == myOrigin) o else o + (childInstance -> childOrigin)
+        }
+      case None => childrenOrigins
+    }
+  }
+}
+
diff --git a/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala b/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala
new file mode 100644
index 00000000..da1129bc
--- /dev/null
+++ b/src/main/scala/firrtl/passes/clocklist/RemoveAllButClocks.scala
@@ -0,0 +1,39 @@
+// See license file for details
+
+package firrtl.passes
+package clocklist
+
+import firrtl._
+import firrtl.ir._
+import Annotations._
+import Utils.error
+import java.io.{File, CharArrayWriter, PrintWriter, Writer}
+import wiring.WiringUtils.{getChildrenMap, countInstances, ChildrenMap, getLineage}
+import wiring.Lineage
+import ClockListUtils._
+import Utils._
+import memlib.AnalysisUtils._
+import memlib._
+import Mappers._
+
+/** Remove all statements and ports (except instances/whens/blocks) whose
+ *  expressions do not relate to ground types.
+ */
+object RemoveAllButClocks extends Pass {
+  def name = this.getClass.getSimpleName
+  def onStmt(s: Statement): Statement = (s map onStmt) match {
+    case DefWire(i, n, ClockType) => s
+    case DefNode(i, n, value) if value.tpe == ClockType => s
+    case Connect(i, l, r) if l.tpe == ClockType => s
+    case sx: WDefInstance => sx
+    case sx: DefInstance => sx
+    case sx: Block => sx
+    case sx: Conditionally => sx
+    case _ => EmptyStmt
+  }
+  def onModule(m: DefModule): DefModule = m match {
+    case Module(i, n, ps, b) => Module(i, n, ps.filter(_.tpe == ClockType), squashEmpty(onStmt(b)))
+    case ExtModule(i, n, ps, dn, p) => ExtModule(i, n, ps.filter(_.tpe == ClockType), dn, p)
+  }
+  def run(c: Circuit): Circuit = c.copy(modules = c.modules map onModule)
+}
diff --git a/src/main/scala/firrtl/passes/memlib/ReplaceMemTransform.scala b/src/main/scala/firrtl/passes/memlib/ReplaceMemTransform.scala
index d9e8a50d..67b81160 100644
--- a/src/main/scala/firrtl/passes/memlib/ReplaceMemTransform.scala
+++ b/src/main/scala/firrtl/passes/memlib/ReplaceMemTransform.scala
@@ -15,6 +15,7 @@ sealed trait PassOption
 case object InputConfigFileName extends PassOption
 case object OutputConfigFileName extends PassOption
 case object PassCircuitName extends PassOption
+case object PassModuleName extends PassOption
 
 object PassConfigUtil {
   type PassOptionMap = Map[PassOption, String]
@@ -32,6 +33,8 @@ object PassConfigUtil {
           nextPassOption(map + (OutputConfigFileName -> value), tail)
         case "-c" :: value :: tail =>
           nextPassOption(map + (PassCircuitName -> value), tail)
+        case "-m" :: value :: tail =>
+          nextPassOption(map + (PassModuleName -> value), tail)
         case option :: tail =>
           error("Unknown option " + option + usage)
       }
diff --git a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
index e5957e1d..2527ccbe 100644
--- a/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
+++ b/src/main/scala/firrtl/passes/wiring/WiringUtils.scala
@@ -41,6 +41,9 @@ case class Lineage(
     |$tab children: ${children.map(c => tab + "   " + c._2.shortSerialize(tab + "    "))}
     |""".stripMargin
 
+  def foldLeft[B](z: B)(op: (B, (String, Lineage)) => B): B = 
+    this.children.foldLeft(z)(op)
+
   def serialize(tab: String): String = s"""
     |$tab name: $name,
     |$tab source: $source,
diff --git a/src/test/scala/firrtlTests/ClockListTests.scala b/src/test/scala/firrtlTests/ClockListTests.scala
new file mode 100644
index 00000000..534aab89
--- /dev/null
+++ b/src/test/scala/firrtlTests/ClockListTests.scala
@@ -0,0 +1,87 @@
+package firrtlTests
+
+import java.io._
+import org.scalatest._
+import org.scalatest.prop._
+import firrtl._
+import firrtl.ir.Circuit
+import firrtl.passes._
+import firrtl.Parser.IgnoreInfo
+import Annotations._
+import clocklist._
+
+class ClockListTests extends FirrtlFlatSpec {
+  private def executeTest(input: String, expected: Seq[String], passes: Seq[Pass]) = {
+    val c = passes.foldLeft(Parser.parse(input.split("\n").toIterator)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val lines = c.serialize.split("\n") map normalized
+
+    expected foreach { e =>
+      lines should contain(e)
+    }
+  }
+
+  def passes = Seq(
+    ToWorkingIR,
+    ResolveKinds,
+    InferTypes,
+    ResolveGenders,
+    InferWidths
+  )
+
+  "Getting clock list" should "work" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    input clock: Clock
+        |    inst ht of HTop
+        |    ht.clock <= clock
+        |  module HTop :
+        |    input clock: Clock
+        |    inst h of Hurricane
+        |    h.clkTop <= clock
+        |    h.clock <= h.clk1
+        |  module Hurricane :
+        |    input clock: Clock
+        |    input clkTop: Clock
+        |    output clk1: Clock
+        |    inst b of B
+        |    inst c of C
+        |    inst clkGen of ClockGen
+        |    clkGen.clkTop <= clkTop
+        |    clk1 <= clkGen.clk1
+        |    b.clock <= clkGen.clk2
+        |    c.clock <= clkGen.clk3
+        |  module B :
+        |    input clock: Clock
+        |    reg r: UInt<5>, clock
+        |    inst d of D
+        |    d.clock <= clock
+        |  module C :
+        |    input clock: Clock
+        |    reg r: UInt<5>, clock
+        |  module D :
+        |    input clock: Clock
+        |    reg r: UInt<5>, clock
+        |  extmodule ClockGen :
+        |    input clkTop: Clock
+        |    output clk1: Clock
+        |    output clk2: Clock
+        |    output clk3: Clock
+        |""".stripMargin
+    val check = 
+  """Sourcelist: List(h$clkGen$clk1, h$clkGen$clk2, h$clkGen$clk3, clock) 
+    |Good Origin of clock is clock
+    |Good Origin of h.clock is h$clkGen.clk1
+    |Good Origin of h$b.clock is h$clkGen.clk2
+    |Good Origin of h$c.clock is h$clkGen.clk3
+    |""".stripMargin
+    val c = passes.foldLeft(parse(input)) {
+      (c: Circuit, p: Pass) => p.run(c)
+    }
+    val writer = new StringWriter()
+    val retC = new ClockList("HTop", writer).run(c)
+    (writer.toString()) should be (check)
+  }
+}