Da steve101 tree reduce (#485)

* Add a tree reduce function to Vec

* Change function names of reduce operation function in Vec

* Change reference to single layer operation in Vec.reduce

* Commint name change for pair macro

* Remove pair, call not necessary and can just be used from grouped(2) and map

* Changed to reduceTree, added default identity function for single reduce.

* Change style of Vec.reduceTree and tests to chisel3 and canonical Scala style

* Cleanup Vec initialization, implicitCompileOptions

1 files changed, 31 insertions, 0 deletions

diff --git a/chiselFrontend/src/main/scala/chisel3/Aggregate.scala b/chiselFrontend/src/main/scala/chisel3/Aggregate.scala
index dfba1caf..4640cb0f 100644
--- a/chiselFrontend/src/main/scala/chisel3/Aggregate.scala
+++ b/chiselFrontend/src/main/scala/chisel3/Aggregate.scala
@@ -263,6 +263,37 @@ sealed class Vec[T <: Data] private[chisel3] (gen: => T, val length: Int)
     // scalastyle:on if.brace
     PString("Vec(") + Printables(elts) + PString(")")
   }
+
+  /** A reduce operation in a tree like structure instead of sequentially
+    * @example An adder tree
+    * {{{
+    * val sumOut = inputNums.reduceTree((a: T, b: T) => (a + b))
+    * }}}
+    */
+  def reduceTree(redOp: (T, T) => T): T = macro VecTransform.reduceTreeDefault
+
+  /** A reduce operation in a tree like structure instead of sequentially
+    * @example A pipelined adder tree
+    * {{{
+    * val sumOut = inputNums.reduceTree(
+    *   (a: T, b: T) => RegNext(a + b),
+    *   (a: T) => RegNext(a)
+    * )
+    * }}}
+    */
+  def reduceTree(redOp: (T, T) => T, layerOp: (T) => T): T = macro VecTransform.reduceTree
+
+  def do_reduceTree(redOp: (T, T) => T, layerOp: (T) => T = (x: T) => x)
+                   (implicit sourceInfo: SourceInfo, compileOptions: CompileOptions) : T = {
+    require(!isEmpty, "Cannot apply reduction on a vec of size 0")
+    var curLayer = this
+    while (curLayer.length > 1) {
+      curLayer = VecInit(curLayer.grouped(2).map( x =>
+        if (x.length == 1) layerOp(x(0)) else redOp(x(0), x(1))
+      ).toSeq)
+    }
+    curLayer(0)
+  }
 }
 
 object VecInit extends SourceInfoDoc {