Add primitive dead code elimination pass

3 files changed, 83 insertions, 1 deletions

diff --git a/src/main/scala/firrtl/Compiler.scala b/src/main/scala/firrtl/Compiler.scala
index c0fa78f0..f87e2c71 100644
--- a/src/main/scala/firrtl/Compiler.scala
+++ b/src/main/scala/firrtl/Compiler.scala
@@ -74,7 +74,6 @@ object VerilogCompiler extends Compiler {
     ExpandWhens,
     CheckInitialization,   
     Legalize,
-    ConstProp,
     ResolveKinds,
     InferTypes,
     ResolveGenders,
@@ -84,6 +83,8 @@ object VerilogCompiler extends Compiler {
     InferTypes,
     ResolveGenders,
     InferWidths,
+    ConstProp,
+    DeadCodeElimination,
     VerilogWrap,
     SplitExp,
     VerilogRename
diff --git a/src/main/scala/firrtl/Emitter.scala b/src/main/scala/firrtl/Emitter.scala
index f6354ee6..fd9bfdc3 100644
--- a/src/main/scala/firrtl/Emitter.scala
+++ b/src/main/scala/firrtl/Emitter.scala
@@ -392,6 +392,7 @@ class VerilogEmitter extends Emitter {
       }
       def build_streams (s:Stmt) : Stmt = {
          s match {
+            case (s:Empty) => s
             case (s:Connect) => s
             case (s:DefWire) => 
                declare("wire",s.name,s.tpe)
diff --git a/src/main/scala/firrtl/passes/DeadCodeElimination.scala b/src/main/scala/firrtl/passes/DeadCodeElimination.scala
new file mode 100644
index 00000000..98ef296e
--- /dev/null
+++ b/src/main/scala/firrtl/passes/DeadCodeElimination.scala
@@ -0,0 +1,80 @@
+/*
+Copyright (c) 2014 - 2016 The Regents of the University of
+California (Regents). All Rights Reserved.  Redistribution and use in
+source and binary forms, with or without modification, are permitted
+provided that the following conditions are met:
+   * Redistributions of source code must retain the above
+     copyright notice, this list of conditions and the following
+     two paragraphs of disclaimer.
+   * Redistributions in binary form must reproduce the above
+     copyright notice, this list of conditions and the following
+     two paragraphs of disclaimer in the documentation and/or other materials
+     provided with the distribution.
+   * Neither the name of the Regents nor the names of its contributors
+     may be used to endorse or promote products derived from this
+     software without specific prior written permission.
+IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
+SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS,
+ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
+REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF
+ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION
+TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
+MODIFICATIONS.
+*/
+
+package firrtl.passes
+
+import firrtl._
+import firrtl.Utils._
+import firrtl.Mappers._
+
+import annotation.tailrec
+
+object DeadCodeElimination extends Pass {
+  def name = "Dead Code Elimination"
+
+  @tailrec
+  private def dce(s: Stmt): Stmt = {
+    val referenced = collection.mutable.HashSet[String]()
+    var nEliminated = 0L
+
+    def checkExpressionUse(e: Expression): Expression = {
+      e match {
+        case WRef(name, _, _, _) => referenced += name
+        case _ => e map checkExpressionUse
+      }
+      e
+    }
+
+    def checkUse(s: Stmt): Stmt = s map checkUse map checkExpressionUse
+
+    def maybeEliminate(x: Stmt, name: String) =
+      if (referenced(name)) x
+      else {
+        nEliminated += 1
+        Empty()
+      }
+
+    def removeUnused(s: Stmt): Stmt = s match {
+      case x: DefRegister => maybeEliminate(x, x.name)
+      case x: DefWire => maybeEliminate(x, x.name)
+      case x: DefNode => maybeEliminate(x, x.name)
+      case x => s map removeUnused
+    }
+
+    checkUse(s)
+    val res = removeUnused(s)
+    if (nEliminated > 0) dce(res) else res
+  }
+
+  def run(c: Circuit): Circuit = {
+    val modulesx = c.modules.map {
+      case m: ExModule => m
+      case m: InModule => InModule(m.info, m.name, m.ports, dce(m.body))
+    }
+    Circuit(c.info, modulesx, c.main)
+  }
+}