From a16a8a52a3b2d72d80a27434217aaeba7be2d3a8 Mon Sep 17 00:00:00 2001
From: mergify[bot]
Date: Wed, 20 Apr 2022 21:10:07 +0000
Subject: Generate a balanced tree with reduceTree (#2318) (#2499)

The difference in logic depth for various paths now has a maximum of 1.

Also make treeReduce order the same for 2.12 and 2.13

.grouped(_) returns an Iterator
.toSeq on an Iterator returns a Stream in 2.12 and a List in 2.13
This can lead to changes in order when bumping from 2.12 to 2.13 that
can be avoided by simply using an eager collection explicitly.

Co-authored-by: Jack Koenig <koenig@sifive.com>
(cherry picked from commit 6975f77f3325dec46c613552eac663c29011a67c)

Co-authored-by: Martin Schoeberl <martin@jopdesign.com>---
 core/src/main/scala/chisel3/Aggregate.scala | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

(limited to 'core/src/main')

diff --git a/core/src/main/scala/chisel3/Aggregate.scala b/core/src/main/scala/chisel3/Aggregate.scala
index 06ae36f3..cc5b83d9 100644
--- a/core/src/main/scala/chisel3/Aggregate.scala
+++ b/core/src/main/scala/chisel3/Aggregate.scala
@@ -14,6 +14,7 @@ import chisel3.internal.Builder.pushCommand
 import chisel3.internal.firrtl._
 import chisel3.internal.sourceinfo._
 
+import java.lang.Math.{floor, log10, pow}
 import scala.collection.mutable
 
 class AliasedAggregateFieldException(message: String) extends ChiselException(message)
@@ -381,11 +382,30 @@ sealed class Vec[T <: Data] private[chisel3] (gen: => T, val length: Int) extend
     compileOptions:      CompileOptions
   ): T = {
     require(!isEmpty, "Cannot apply reduction on a vec of size 0")
-    var curLayer: Seq[T] = this
-    while (curLayer.length > 1) {
-      curLayer = curLayer.grouped(2).map(x => if (x.length == 1) layerOp(x(0)) else redOp(x(0), x(1))).toSeq
+
+    def recReduce[T](s: Seq[T], op: (T, T) => T, lop: (T) => T): T = {
+
+      val n = s.length
+      n match {
+        case 1 => lop(s(0))
+        case 2 => op(s(0), s(1))
+        case _ =>
+          val m = pow(2, floor(log10(n - 1) / log10(2))).toInt // number of nodes in next level, will be a power of 2
+          val p = 2 * m - n // number of nodes promoted
+
+          val l = s.take(p).map(lop)
+          val r = s
+            .drop(p)
+            .grouped(2)
+            .map {
+              case Seq(a, b) => op(a, b)
+            }
+            .toVector
+          recReduce(l ++ r, op, lop)
+      }
     }
-    curLayer(0)
+
+    recReduce(this, redOp, layerOp)
   }
 
   /** Creates a Vec literal of this type with specified values. this must be a chisel type.
-- 
cgit v1.2.3