From 317115b7a0ce21d5848e985988c777f9931af241 Mon Sep 17 00:00:00 2001 From: Jack Koenig Date: Mon, 12 Jun 2017 12:20:42 -0700 Subject: Move CheckCombLoops from passes/ to transforms/ --- src/main/scala/firrtl/LoweringCompilers.scala | 2 +- src/main/scala/firrtl/passes/CheckCombLoops.scala | 216 -------------------- .../scala/firrtl/transforms/CheckCombLoops.scala | 217 +++++++++++++++++++++ 3 files changed, 218 insertions(+), 217 deletions(-) delete mode 100644 src/main/scala/firrtl/passes/CheckCombLoops.scala create mode 100644 src/main/scala/firrtl/transforms/CheckCombLoops.scala (limited to 'src/main/scala') diff --git a/src/main/scala/firrtl/LoweringCompilers.scala b/src/main/scala/firrtl/LoweringCompilers.scala index 161c2771..0df052af 100644 --- a/src/main/scala/firrtl/LoweringCompilers.scala +++ b/src/main/scala/firrtl/LoweringCompilers.scala @@ -85,7 +85,7 @@ class MiddleFirrtlToLowFirrtl extends CoreTransform { passes.ResolveGenders, passes.InferWidths, passes.Legalize, - new passes.CheckCombLoops) + new firrtl.transforms.CheckCombLoops) } /** Runs a series of optimization passes on LowFirrtl diff --git a/src/main/scala/firrtl/passes/CheckCombLoops.scala b/src/main/scala/firrtl/passes/CheckCombLoops.scala deleted file mode 100644 index da5cc549..00000000 --- a/src/main/scala/firrtl/passes/CheckCombLoops.scala +++ /dev/null @@ -1,216 +0,0 @@ -// See LICENSE for license details. - -package firrtl.passes - -import scala.collection.mutable -import scala.collection.immutable.HashSet -import scala.collection.immutable.HashMap -import annotation.tailrec - -import firrtl._ -import firrtl.ir._ -import firrtl.Mappers._ -import firrtl.Utils.throwInternalError -import firrtl.graph.{MutableDiGraph,DiGraph} -import firrtl.analyses.InstanceGraph - -object CheckCombLoops { - class CombLoopException(info: Info, mname: String, cycle: Seq[String]) extends PassException( - s"$info: [module $mname] Combinational loop detected:\n" + cycle.mkString("\n")) - -} - -/** Finds and detects combinational logic loops in a circuit, if any - * exist. Returns the input circuit with no modifications. - * - * @throws a CombLoopException if a loop is found - * @note Input form: Low FIRRTL - * @note Output form: Low FIRRTL (identity transform) - * @note The pass looks for loops through combinational-read memories - * @note The pass cannot find loops that pass through ExtModules - * @note The pass will throw exceptions on "false paths" - */ -class CheckCombLoops extends Transform { - def inputForm = LowForm - def outputForm = LowForm - - import CheckCombLoops._ - - /* - * A case class that represents a net in the circuit. This is - * necessary since combinational loop checking is an analysis on the - * netlist of the circuit; the fields are specialized for low - * FIRRTL. Since all wires are ground types, a given ground type net - * may only be a subfield of an instance or a memory - * port. Therefore, it is uniquely specified within its module - * context by its name, its optional parent instance (a WDefInstance - * or WDefMemory), and its optional memory port name. - */ - private case class LogicNode(name: String, inst: Option[String] = None, memport: Option[String] = None) - - private def toLogicNode(e: Expression): LogicNode = e match { - case r: WRef => - LogicNode(r.name) - case s: WSubField => - s.expr match { - case modref: WRef => - LogicNode(s.name,Some(modref.name)) - case memport: WSubField => - memport.expr match { - case memref: WRef => - LogicNode(s.name,Some(memref.name),Some(memport.name)) - case _ => throwInternalError - } - case _ => throwInternalError - } - } - - private def getExprDeps(deps: mutable.Set[LogicNode])(e: Expression): Expression = e match { - case r: WRef => - deps += toLogicNode(r) - r - case s: WSubField => - deps += toLogicNode(s) - s - case _ => - e map getExprDeps(deps) - } - - private def getStmtDeps( - simplifiedModules: mutable.Map[String,DiGraph[LogicNode]], - deps: MutableDiGraph[LogicNode])(s: Statement): Statement = { - s match { - case Connect(_,loc,expr) => - val lhs = toLogicNode(loc) - if (deps.contains(lhs)) { - getExprDeps(deps.getEdges(lhs))(expr) - } - case w: DefWire => - deps.addVertex(LogicNode(w.name)) - case n: DefNode => - val lhs = LogicNode(n.name) - deps.addVertex(lhs) - getExprDeps(deps.getEdges(lhs))(n.value) - case m: DefMemory if (m.readLatency == 0) => - for (rp <- m.readers) { - val dataNode = deps.addVertex(LogicNode("data",Some(m.name),Some(rp))) - deps.addEdge(dataNode, deps.addVertex(LogicNode("addr",Some(m.name),Some(rp)))) - deps.addEdge(dataNode, deps.addVertex(LogicNode("en",Some(m.name),Some(rp)))) - } - case i: WDefInstance => - val iGraph = simplifiedModules(i.module).transformNodes(n => n.copy(inst = Some(i.name))) - for (v <- iGraph.getVertices) { - deps.addVertex(v) - iGraph.getEdges(v).foreach { deps.addEdge(v,_) } - } - case _ => - s map getStmtDeps(simplifiedModules,deps) - } - s - } - - /* - * Recover the full path from a path passing through simplified - * instances. Since edges may pass through simplified instances, the - * hierarchy that the path passes through must be recursively - * recovered. - */ - private def expandInstancePaths( - m: String, - moduleGraphs: mutable.Map[String,DiGraph[LogicNode]], - moduleDeps: Map[String, Map[String,String]], - prefix: Seq[String], - path: Seq[LogicNode]): Seq[String] = { - def absNodeName(prefix: Seq[String], n: LogicNode) = - (prefix ++ n.inst ++ n.memport :+ n.name).mkString(".") - val pathNodes = (path zip path.tail) map { case (a, b) => - if (a.inst.isDefined && !a.memport.isDefined && a.inst == b.inst) { - val child = moduleDeps(m)(a.inst.get) - val newprefix = prefix :+ a.inst.get - val subpath = moduleGraphs(child).path(b.copy(inst=None),a.copy(inst=None)).tail.reverse - expandInstancePaths(child,moduleGraphs,moduleDeps,newprefix,subpath) - } else { - Seq(absNodeName(prefix,a)) - } - } - pathNodes.flatten :+ absNodeName(prefix, path.last) - } - - /* - * An SCC may contain more than one loop. In this case, the sequence - * of nodes forming the SCC cannot be interpreted as a simple - * cycle. However, it is desirable to print an error consisting of a - * loop rather than an arbitrary ordering of the SCC. This function - * operates on a pruned subgraph composed only of the SCC and finds - * a simple cycle by performing an arbitrary walk. - */ - private def findCycleInSCC[T](sccGraph: DiGraph[T]): Seq[T] = { - val walk = new mutable.ArrayBuffer[T] - val visited = new mutable.HashSet[T] - var current = sccGraph.getVertices.head - while (!visited.contains(current)) { - walk += current - visited += current - current = sccGraph.getEdges(current).head - } - walk.drop(walk.indexOf(current)).toSeq :+ current - } - - /* - * This implementation of combinational loop detection avoids ever - * generating a full netlist from the FIRRTL circuit. Instead, each - * module is converted to a netlist and analyzed locally, with its - * subinstances represented by trivial, simplified subgraphs. The - * overall outline of the process is: - * - * 1. Create a graph of module instance dependances - - * 2. Linearize this acyclic graph - * - * 3. Generate a local netlist; replace any instances with - * simplified subgraphs representing connectivity of their IOs - * - * 4. Check for nontrivial strongly connected components - * - * 5. Create a reduced representation of the netlist with only the - * module IOs as nodes, where output X (which must be a ground type, - * as only low FIRRTL is supported) will have an edge to input Y if - * and only if it combinationally depends on input Y. Associate this - * reduced graph with the module for future use. - */ - def run(c: Circuit): Circuit = { - val errors = new Errors() - /* TODO(magyar): deal with exmodules! No pass warnings currently - * exist. Maybe warn when iterating through modules. - */ - val moduleMap = c.modules.map({m => (m.name,m) }).toMap - val iGraph = new InstanceGraph(c) - val moduleDeps = iGraph.graph.edges.map{ case (k,v) => (k.module, (v map { i => (i.name, i.module) }).toMap) } - val topoSortedModules = iGraph.graph.transformNodes(_.module).linearize.reverse map { moduleMap(_) } - val moduleGraphs = new mutable.HashMap[String,DiGraph[LogicNode]] - val simplifiedModuleGraphs = new mutable.HashMap[String,DiGraph[LogicNode]] - for (m <- topoSortedModules) { - val internalDeps = new MutableDiGraph[LogicNode] - m.ports.foreach({ p => internalDeps.addVertex(LogicNode(p.name)) }) - m map getStmtDeps(simplifiedModuleGraphs, internalDeps) - val moduleGraph = DiGraph(internalDeps) - moduleGraphs(m.name) = moduleGraph - simplifiedModuleGraphs(m.name) = moduleGraphs(m.name).simplify((m.ports map { p => LogicNode(p.name) }).toSet) - for (scc <- moduleGraphs(m.name).findSCCs.filter(_.length > 1)) { - val sccSubgraph = moduleGraphs(m.name).subgraph(scc.toSet) - val cycle = findCycleInSCC(sccSubgraph) - (cycle zip cycle.tail).foreach({ case (a,b) => require(moduleGraph.getEdges(a).contains(b)) }) - val expandedCycle = expandInstancePaths(m.name,moduleGraphs,moduleDeps,Seq(m.name),cycle.reverse) - errors.append(new CombLoopException(m.info, m.name, expandedCycle)) - } - } - errors.trigger() - c - } - - def execute(state: CircuitState): CircuitState = { - val result = run(state.circuit) - CircuitState(result, outputForm, state.annotations, state.renames) - } - -} diff --git a/src/main/scala/firrtl/transforms/CheckCombLoops.scala b/src/main/scala/firrtl/transforms/CheckCombLoops.scala new file mode 100644 index 00000000..d0eec02c --- /dev/null +++ b/src/main/scala/firrtl/transforms/CheckCombLoops.scala @@ -0,0 +1,217 @@ +// See LICENSE for license details. + +package firrtl.transforms + +import scala.collection.mutable +import scala.collection.immutable.HashSet +import scala.collection.immutable.HashMap +import annotation.tailrec + +import firrtl._ +import firrtl.ir._ +import firrtl.passes.{Errors, PassException} +import firrtl.Mappers._ +import firrtl.Utils.throwInternalError +import firrtl.graph.{MutableDiGraph,DiGraph} +import firrtl.analyses.InstanceGraph + +object CheckCombLoops { + class CombLoopException(info: Info, mname: String, cycle: Seq[String]) extends PassException( + s"$info: [module $mname] Combinational loop detected:\n" + cycle.mkString("\n")) + +} + +/** Finds and detects combinational logic loops in a circuit, if any + * exist. Returns the input circuit with no modifications. + * + * @throws a CombLoopException if a loop is found + * @note Input form: Low FIRRTL + * @note Output form: Low FIRRTL (identity transform) + * @note The pass looks for loops through combinational-read memories + * @note The pass cannot find loops that pass through ExtModules + * @note The pass will throw exceptions on "false paths" + */ +class CheckCombLoops extends Transform { + def inputForm = LowForm + def outputForm = LowForm + + import CheckCombLoops._ + + /* + * A case class that represents a net in the circuit. This is + * necessary since combinational loop checking is an analysis on the + * netlist of the circuit; the fields are specialized for low + * FIRRTL. Since all wires are ground types, a given ground type net + * may only be a subfield of an instance or a memory + * port. Therefore, it is uniquely specified within its module + * context by its name, its optional parent instance (a WDefInstance + * or WDefMemory), and its optional memory port name. + */ + private case class LogicNode(name: String, inst: Option[String] = None, memport: Option[String] = None) + + private def toLogicNode(e: Expression): LogicNode = e match { + case r: WRef => + LogicNode(r.name) + case s: WSubField => + s.expr match { + case modref: WRef => + LogicNode(s.name,Some(modref.name)) + case memport: WSubField => + memport.expr match { + case memref: WRef => + LogicNode(s.name,Some(memref.name),Some(memport.name)) + case _ => throwInternalError + } + case _ => throwInternalError + } + } + + private def getExprDeps(deps: mutable.Set[LogicNode])(e: Expression): Expression = e match { + case r: WRef => + deps += toLogicNode(r) + r + case s: WSubField => + deps += toLogicNode(s) + s + case _ => + e map getExprDeps(deps) + } + + private def getStmtDeps( + simplifiedModules: mutable.Map[String,DiGraph[LogicNode]], + deps: MutableDiGraph[LogicNode])(s: Statement): Statement = { + s match { + case Connect(_,loc,expr) => + val lhs = toLogicNode(loc) + if (deps.contains(lhs)) { + getExprDeps(deps.getEdges(lhs))(expr) + } + case w: DefWire => + deps.addVertex(LogicNode(w.name)) + case n: DefNode => + val lhs = LogicNode(n.name) + deps.addVertex(lhs) + getExprDeps(deps.getEdges(lhs))(n.value) + case m: DefMemory if (m.readLatency == 0) => + for (rp <- m.readers) { + val dataNode = deps.addVertex(LogicNode("data",Some(m.name),Some(rp))) + deps.addEdge(dataNode, deps.addVertex(LogicNode("addr",Some(m.name),Some(rp)))) + deps.addEdge(dataNode, deps.addVertex(LogicNode("en",Some(m.name),Some(rp)))) + } + case i: WDefInstance => + val iGraph = simplifiedModules(i.module).transformNodes(n => n.copy(inst = Some(i.name))) + for (v <- iGraph.getVertices) { + deps.addVertex(v) + iGraph.getEdges(v).foreach { deps.addEdge(v,_) } + } + case _ => + s map getStmtDeps(simplifiedModules,deps) + } + s + } + + /* + * Recover the full path from a path passing through simplified + * instances. Since edges may pass through simplified instances, the + * hierarchy that the path passes through must be recursively + * recovered. + */ + private def expandInstancePaths( + m: String, + moduleGraphs: mutable.Map[String,DiGraph[LogicNode]], + moduleDeps: Map[String, Map[String,String]], + prefix: Seq[String], + path: Seq[LogicNode]): Seq[String] = { + def absNodeName(prefix: Seq[String], n: LogicNode) = + (prefix ++ n.inst ++ n.memport :+ n.name).mkString(".") + val pathNodes = (path zip path.tail) map { case (a, b) => + if (a.inst.isDefined && !a.memport.isDefined && a.inst == b.inst) { + val child = moduleDeps(m)(a.inst.get) + val newprefix = prefix :+ a.inst.get + val subpath = moduleGraphs(child).path(b.copy(inst=None),a.copy(inst=None)).tail.reverse + expandInstancePaths(child,moduleGraphs,moduleDeps,newprefix,subpath) + } else { + Seq(absNodeName(prefix,a)) + } + } + pathNodes.flatten :+ absNodeName(prefix, path.last) + } + + /* + * An SCC may contain more than one loop. In this case, the sequence + * of nodes forming the SCC cannot be interpreted as a simple + * cycle. However, it is desirable to print an error consisting of a + * loop rather than an arbitrary ordering of the SCC. This function + * operates on a pruned subgraph composed only of the SCC and finds + * a simple cycle by performing an arbitrary walk. + */ + private def findCycleInSCC[T](sccGraph: DiGraph[T]): Seq[T] = { + val walk = new mutable.ArrayBuffer[T] + val visited = new mutable.HashSet[T] + var current = sccGraph.getVertices.head + while (!visited.contains(current)) { + walk += current + visited += current + current = sccGraph.getEdges(current).head + } + walk.drop(walk.indexOf(current)).toSeq :+ current + } + + /* + * This implementation of combinational loop detection avoids ever + * generating a full netlist from the FIRRTL circuit. Instead, each + * module is converted to a netlist and analyzed locally, with its + * subinstances represented by trivial, simplified subgraphs. The + * overall outline of the process is: + * + * 1. Create a graph of module instance dependances + + * 2. Linearize this acyclic graph + * + * 3. Generate a local netlist; replace any instances with + * simplified subgraphs representing connectivity of their IOs + * + * 4. Check for nontrivial strongly connected components + * + * 5. Create a reduced representation of the netlist with only the + * module IOs as nodes, where output X (which must be a ground type, + * as only low FIRRTL is supported) will have an edge to input Y if + * and only if it combinationally depends on input Y. Associate this + * reduced graph with the module for future use. + */ + def run(c: Circuit): Circuit = { + val errors = new Errors() + /* TODO(magyar): deal with exmodules! No pass warnings currently + * exist. Maybe warn when iterating through modules. + */ + val moduleMap = c.modules.map({m => (m.name,m) }).toMap + val iGraph = new InstanceGraph(c) + val moduleDeps = iGraph.graph.edges.map{ case (k,v) => (k.module, (v map { i => (i.name, i.module) }).toMap) } + val topoSortedModules = iGraph.graph.transformNodes(_.module).linearize.reverse map { moduleMap(_) } + val moduleGraphs = new mutable.HashMap[String,DiGraph[LogicNode]] + val simplifiedModuleGraphs = new mutable.HashMap[String,DiGraph[LogicNode]] + for (m <- topoSortedModules) { + val internalDeps = new MutableDiGraph[LogicNode] + m.ports.foreach({ p => internalDeps.addVertex(LogicNode(p.name)) }) + m map getStmtDeps(simplifiedModuleGraphs, internalDeps) + val moduleGraph = DiGraph(internalDeps) + moduleGraphs(m.name) = moduleGraph + simplifiedModuleGraphs(m.name) = moduleGraphs(m.name).simplify((m.ports map { p => LogicNode(p.name) }).toSet) + for (scc <- moduleGraphs(m.name).findSCCs.filter(_.length > 1)) { + val sccSubgraph = moduleGraphs(m.name).subgraph(scc.toSet) + val cycle = findCycleInSCC(sccSubgraph) + (cycle zip cycle.tail).foreach({ case (a,b) => require(moduleGraph.getEdges(a).contains(b)) }) + val expandedCycle = expandInstancePaths(m.name,moduleGraphs,moduleDeps,Seq(m.name),cycle.reverse) + errors.append(new CombLoopException(m.info, m.name, expandedCycle)) + } + } + errors.trigger() + c + } + + def execute(state: CircuitState): CircuitState = { + val result = run(state.circuit) + CircuitState(result, outputForm, state.annotations, state.renames) + } + +} -- cgit v1.2.3