From 83f53a3a0cdcfc7537e923b827ab820205025d45 Mon Sep 17 00:00:00 2001
From: Andrew Waterman
Date: Fri, 10 Jun 2016 13:39:18 -0700
Subject: Avoid exponential growth in reg code emission

In 7afe9f6180a53fd9f024c67d78289689a601c8b7, I reintroduced a performance
pathology when recursing through Mux trees.  This patch prevents
redundantly expanding the same Mux more than a constant number of times,
preserving linear runtime but still resulting in acceptable QoR.
---
 src/main/scala/firrtl/Emitter.scala | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

(limited to 'src')

diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index eb8eba32..f871c82a 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -319,9 +319,22 @@ class VerilogEmitter extends Emitter {
          assigns += Seq("`endif")
       }
       def update_and_reset(r: Expression, clk: Expression, reset: Expression, init: Expression) = {
+        // We want to flatten Mux trees for reg updates into if-trees for
+        // improved QoR for conditional updates.  However, unbounded recursion
+        // would take exponential time, so don't redundantly flatten the same
+        // Mux more than a bounded number of times, preserving linear runtime.
+        // The threshold is empirical but ample.
+        val flattenThreshold = 4
+        val numTimesFlattened = collection.mutable.HashMap[Mux, Int]()
+        def canFlatten(m: Mux) = {
+          val n = numTimesFlattened.getOrElse(m, 0)
+          numTimesFlattened(m) = n + 1
+          n < flattenThreshold
+        }
+
         def addUpdate(e: Expression, tabs: String): Seq[Seq[Any]] = {
           netlist.getOrElse(e, e) match {
-            case m: Mux => {
+            case m: Mux if canFlatten(m) => {
               val ifStatement = Seq(tabs, "if(", m.cond, ") begin")
               val trueCase = addUpdate(m.tval, tabs + tab)
               val elseStatement = Seq(tabs, "end else begin")
-- 
cgit v1.2.3