Improve performance of CSE pass

Repeated calls to hashCode take most of the runtime, so cache it.

2 files changed, 14 insertions, 1 deletions

diff --git a/src/main/scala/firrtl/Utils.scala b/src/main/scala/firrtl/Utils.scala
index 390a99a7..bcf75882 100644
--- a/src/main/scala/firrtl/Utils.scala
+++ b/src/main/scala/firrtl/Utils.scala
@@ -954,3 +954,16 @@ object Utils {
       ("PRINTF_COND" -> true) +
       ("VCS" -> true)
 }
+
+object MemoizedHash {
+  implicit def convertTo[T](e: T): MemoizedHash[T] = new MemoizedHash(e)
+  implicit def convertFrom[T](f: MemoizedHash[T]): T = f.t
+}
+
+class MemoizedHash[T](val t: T) {
+  override lazy val hashCode = t.hashCode
+  override def equals(that: Any) = that match {
+    case x: MemoizedHash[_] => t equals x.t
+    case _ => false
+  }
+}
diff --git a/src/main/scala/firrtl/passes/CommonSubexpressionElimination.scala b/src/main/scala/firrtl/passes/CommonSubexpressionElimination.scala
index 7dbc805a..717d95e8 100644
--- a/src/main/scala/firrtl/passes/CommonSubexpressionElimination.scala
+++ b/src/main/scala/firrtl/passes/CommonSubexpressionElimination.scala
@@ -38,7 +38,7 @@ object CommonSubexpressionElimination extends Pass {
 
   private def cseOnce(s: Stmt): (Stmt, Long) = {
     var nEliminated = 0L
-    val expressions = collection.mutable.HashMap[Expression, String]()
+    val expressions = collection.mutable.HashMap[MemoizedHash[Expression], String]()
     val nodes = collection.mutable.HashMap[String, Expression]()
 
     def recordNodes(s: Stmt): Stmt = s match {