From c90be4ea06faf9a39c85f38e932d29fe63eb4b37 Mon Sep 17 00:00:00 2001
From: Andrew Waterman
Date: Thu, 7 Jul 2016 15:41:10 -0700
Subject: Improve QoR for Log2

For reasonable circuit delay, need to divide & conquer.
---
 src/main/scala/chisel3/util/CircuitMath.scala | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/src/main/scala/chisel3/util/CircuitMath.scala b/src/main/scala/chisel3/util/CircuitMath.scala
index b5be03bf..a64447d9 100644
--- a/src/main/scala/chisel3/util/CircuitMath.scala
+++ b/src/main/scala/chisel3/util/CircuitMath.scala
@@ -19,10 +19,18 @@ object Log2 {
       UInt(0)
     } else if (width == 2) {
       x(1)
-    } else {
+    } else if (width <= divideAndConquerThreshold) {
       Mux(x(width-1), UInt(width-1), apply(x, width-1))
+    } else {
+      val mid = 1 << (log2Ceil(width) - 1)
+      val hi = x(width-1, mid)
+      val lo = x(mid-1, 0)
+      val useHi = hi.orR
+      Cat(useHi, Mux(useHi, Log2(hi, width - mid), Log2(lo, mid)))
     }
   }
 
   def apply(x: Bits): UInt = apply(x, x.getWidth)
+
+  private def divideAndConquerThreshold = 4
 }
-- 
cgit v1.2.3