-
Notifications
You must be signed in to change notification settings - Fork 0
Exploration
Vlad Ureche edited this page Jun 15, 2014
·
2 revisions
To benchmark the code, we took the Fast Fourier Transform example from Rosetta code and used it as the benchmarking target: https://github.com/miniboxing/staging-plugin/blob/master/tests/correctness/src/stagium/testcases/fft.scala
Complex class:
case class Complex(re: Double, im: Double) {
def +(x: Complex): Complex = Complex(re + x.re, im + x.im)
def -(x: Complex): Complex = Complex(re - x.re, im - x.im)
def **(x: Double): Complex = Complex(re * x, im * x)
def *(x: Complex): Complex = Complex(re * x.re - im * x.im, re * x.im + im * x.re)
def /(x: Double): Complex = Complex(re / x, im / x)
override def toString(): String = s"stagium.examples.fft.Complex($re, $im)"
def exp: Complex = Complex.exp(this)
}
object Complex {
def exp(c: Complex) : Complex = {
val r = (cosh(c.re) + sinh(c.re))
Complex(cos(c.im), sin(c.im)) ** r
}
}FFT:
// annotations need to be added since the type inference does not kick in properly when annotations are present
// see https://groups.google.com/forum/#!topic/scala-internals/-hp79CrjQPo for more details
object FFT {
def _fft(cSeq: Seq[Complex @staged], direction: Complex @staged, scalar: Int @staged): Seq[Complex @staged] = {
if (cSeq.length == 1) {
cSeq
} else {
val n = cSeq.length
assume(n % 2 == 0, "The Cooley-Tukey FFT algorithm only works when the length of the input is a power of two.")
val evenOddPairs = cSeq.grouped(2).toSeq
val evens = _fft(evenOddPairs map[Complex @staged, Seq[Complex @staged]] (_(0)), direction, scalar)
val odds = _fft(evenOddPairs map[Complex @staged, Seq[Complex @staged]] (_(1)), direction, scalar)
def leftRightPair(k: Int): (Complex @staged, Complex @staged) = {
val base: Complex @staged = evens(k) / scalar
val offset: Complex @staged = odds(k) * ((direction ** (Pi * k / n)).exp / scalar)
Tuple2[Complex @staged, Complex @staged](base + offset, base - offset)
}
val pairs = (0 until n/2) map leftRightPair
val left = pairs map[Complex @staged, Seq[Complex @staged]] (_._1)
val right = pairs map[Complex @staged, Seq[Complex @staged]] (_._2)
left ++ right
}
}
def fft(cSeq: Seq[Complex @staged]): Seq[Complex @staged] = _fft(cSeq, Complex(0, 2), 1)
def rfft(cSeq: Seq[Complex @staged]): Seq[Complex @staged] = _fft(cSeq, Complex(0, -2), 2)
}As before, we define a __staged object which defines the infix methods required for staging the example. We also add the following test for staging:
// Test for staging
object Test {
def main(args: Array[String]): Unit = {
import FFT._
val fun = function8((e1: Complex @staged, e2: Complex @staged, e3: Complex @staged, e4: Complex @staged, e5: Complex @staged, e6: Complex @staged, e7: Complex @staged, e8: Complex @staged) =>
rfft(fft(Seq[Complex @staged](e1, e2, e3, e4, e5, e6, e7, e8)))(0))
val c = Complex(1.0, 1.0)
fun(c,c,c,c,c,c,c,c)
}
}Running the program returns:
$ st-scalac fft.scala && st-scala stagium.examples.fft.Test
Need to compile and run:
*********************************
{
val x216: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex =
(a1: stagium.examples.fft.Complex, a2: stagium.examples.fft.Complex, a3: stagium.examples.fft.Complex, a4: stagium.examples.fft.Complex, a5: stagium.examples.fft.Complex, a6: stagium.examples.fft.Complex, a7: stagium.examples.fft.Complex, a8: stagium.examples.fft.Complex) => {
val x184: Double = 2.toDouble
val x112: Double = 2.toDouble
val x0: Double = 1.toDouble
val x146: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x47: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x4: Double = 1.toDouble
val x81: Double = 1.toDouble
val x162: Double = 2.toDouble
val x119: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x20: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x121: Double = 2.toDouble
val x27: Double = 1.toDouble
val x13: Double = 1.toDouble
val x56: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x101: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 1.1780972450961724
val x144: Double = 2.toDouble
val x45: Double = 1.toDouble
val x85: Double = 1.toDouble
val x11: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x67: Double = 1.toDouble
val x58: Double = 1.toDouble
val x126: Double = 2.toDouble
val x103: Double = 1.toDouble
val x99: Double = 1.toDouble
val x180: Double = 2.toDouble
val x63: Double = 1.toDouble
val x83: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.39269908169872414
val x153: Double = 2.toDouble
val x166: Double = 2.toDouble
val x38: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x40: Double = 1.toDouble
val x148: Double = 2.toDouble
val x117: Double = 2.toDouble
val x65: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.7853981633974483
val x94: Double = 1.toDouble
val x76: Double = 1.toDouble
val x9: Double = 1.toDouble
val x130: Double = 2.toDouble
val x164: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x182: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x108: Double = 2.toDouble
val x72: Double = 1.toDouble
val x36: Double = 1.toDouble
val x74: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x157: Double = 2.toDouble
val x18: Double = 1.toDouble
val x110: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x155: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x31: Double = 1.toDouble
val x49: Double = 1.toDouble
val x2: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.0
val x54: Double = 1.toDouble
val x29: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.7853981633974483
val x92: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, 2.0) * 0.7853981633974483
val x22: Double = 1.toDouble
val x128: stagium.examples.fft.Complex = stagium.examples.fft.Complex(0.0, -2.0) * 0.0
val x90: Double = 1.toDouble
val x120: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x119)
val x93: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x92)
val x10: stagium.examples.fft.Complex = a3 / x9
val x46: stagium.examples.fft.Complex = a4 / x45
val x39: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x38)
val x1: stagium.examples.fft.Complex = a1 / x0
val x66: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x65)
val x12: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x11)
val x3: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x2)
val x165: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x164)
val x156: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x155)
val x84: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x83)
val x48: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x47)
val x57: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x56)
val x21: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x20)
val x37: stagium.examples.fft.Complex = a2 / x36
val x129: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x128)
val x147: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x146)
val x102: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x101)
val x75: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x74)
val x111: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x110)
val x30: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x29)
val x183: stagium.examples.fft.Complex = stagium.bench.complex.fft.Complex.exp(x182)
val x14: stagium.examples.fft.Complex = x12 / x13
val x131: stagium.examples.fft.Complex = x129 / x130
val x167: stagium.examples.fft.Complex = x165 / x166
val x32: stagium.examples.fft.Complex = x30 / x31
val x113: stagium.examples.fft.Complex = x111 / x112
val x77: stagium.examples.fft.Complex = x75 / x76
val x149: stagium.examples.fft.Complex = x147 / x148
val x104: stagium.examples.fft.Complex = x102 / x103
val x95: stagium.examples.fft.Complex = x93 / x94
val x59: stagium.examples.fft.Complex = x57 / x58
val x5: stagium.examples.fft.Complex = x3 / x4
val x185: stagium.examples.fft.Complex = x183 / x184
val x86: stagium.examples.fft.Complex = x84 / x85
val x23: stagium.examples.fft.Complex = x21 / x22
val x158: stagium.examples.fft.Complex = x156 / x157
val x122: stagium.examples.fft.Complex = x120 / x121
val x41: stagium.examples.fft.Complex = x39 / x40
val x68: stagium.examples.fft.Complex = x66 / x67
val x50: stagium.examples.fft.Complex = x48 / x49
val x42: stagium.examples.fft.Complex = a6 * x41
val x6: stagium.examples.fft.Complex = a5 * x5
val x51: stagium.examples.fft.Complex = a8 * x50
val x15: stagium.examples.fft.Complex = a7 * x14
val x17: stagium.examples.fft.Complex = x10 - x15
val x7: stagium.examples.fft.Complex = x1 + x6
val x52: stagium.examples.fft.Complex = x46 + x51
val x53: stagium.examples.fft.Complex = x46 - x51
val x8: stagium.examples.fft.Complex = x1 - x6
val x44: stagium.examples.fft.Complex = x37 - x42
val x16: stagium.examples.fft.Complex = x10 + x15
val x43: stagium.examples.fft.Complex = x37 + x42
val x60: stagium.examples.fft.Complex = x52 * x59
val x24: stagium.examples.fft.Complex = x16 * x23
val x55: stagium.examples.fft.Complex = x43 / x54
val x69: stagium.examples.fft.Complex = x53 * x68
val x33: stagium.examples.fft.Complex = x17 * x32
val x19: stagium.examples.fft.Complex = x7 / x18
val x64: stagium.examples.fft.Complex = x44 / x63
val x28: stagium.examples.fft.Complex = x8 / x27
val x61: stagium.examples.fft.Complex = x55 + x60
val x35: stagium.examples.fft.Complex = x28 - x33
val x62: stagium.examples.fft.Complex = x55 - x60
val x71: stagium.examples.fft.Complex = x64 - x69
val x70: stagium.examples.fft.Complex = x64 + x69
val x26: stagium.examples.fft.Complex = x19 - x24
val x34: stagium.examples.fft.Complex = x28 + x33
val x25: stagium.examples.fft.Complex = x19 + x24
val x105: stagium.examples.fft.Complex = x71 * x104
val x73: stagium.examples.fft.Complex = x25 / x72
val x96: stagium.examples.fft.Complex = x62 * x95
val x100: stagium.examples.fft.Complex = x35 / x99
val x87: stagium.examples.fft.Complex = x70 * x86
val x91: stagium.examples.fft.Complex = x26 / x90
val x82: stagium.examples.fft.Complex = x34 / x81
val x78: stagium.examples.fft.Complex = x61 * x77
val x97: stagium.examples.fft.Complex = x91 + x96
val x106: stagium.examples.fft.Complex = x100 + x105
val x107: stagium.examples.fft.Complex = x100 - x105
val x89: stagium.examples.fft.Complex = x82 - x87
val x98: stagium.examples.fft.Complex = x91 - x96
val x88: stagium.examples.fft.Complex = x82 + x87
val x79: stagium.examples.fft.Complex = x73 + x78
val x80: stagium.examples.fft.Complex = x73 - x78
val x118: stagium.examples.fft.Complex = x97 / x117
val x159: stagium.examples.fft.Complex = x107 * x158
val x150: stagium.examples.fft.Complex = x89 * x149
val x145: stagium.examples.fft.Complex = x88 / x144
val x123: stagium.examples.fft.Complex = x98 * x122
val x114: stagium.examples.fft.Complex = x80 * x113
val x109: stagium.examples.fft.Complex = x79 / x108
val x154: stagium.examples.fft.Complex = x106 / x153
val x115: stagium.examples.fft.Complex = x109 + x114
val x160: stagium.examples.fft.Complex = x154 + x159
val x151: stagium.examples.fft.Complex = x145 + x150
val x124: stagium.examples.fft.Complex = x118 + x123
val x163: stagium.examples.fft.Complex = x151 / x162
val x127: stagium.examples.fft.Complex = x115 / x126
val x168: stagium.examples.fft.Complex = x160 * x167
val x132: stagium.examples.fft.Complex = x124 * x131
val x169: stagium.examples.fft.Complex = x163 + x168
val x133: stagium.examples.fft.Complex = x127 + x132
val x186: stagium.examples.fft.Complex = x169 * x185
val x181: stagium.examples.fft.Complex = x133 / x180
val x187: stagium.examples.fft.Complex = x181 + x186
x187: stagium.examples.fft.Complex
} // end of code block of 164 instructions
x216: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
} // end of function x216: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
*********************************
<function8 called>We consider it an interesting challenge to reduce the number of instructions in the staged code. Let us start by looking at the signature of fft:
def _fft(cSeq: Seq[Complex @staged], direction: Complex @staged, scalar: Int @staged): Seq[Complex @staged]Actually, since we know the scalar and the direction, they need not be staged:
def _fft(cSeq: Seq[Complex @staged], direction: Complex, scalar: Int): Seq[Complex @staged]Running again, we get:
$ st-scalac fft.scala && st-scala stagium.examples.fft.Test
Need to compile and run:
*********************************
{
val x96: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex =
(a1: stagium.examples.fft.Complex, a2: stagium.examples.fft.Complex, a3: stagium.examples.fft.Complex, a4: stagium.examples.fft.Complex, a5: stagium.examples.fft.Complex, a6: stagium.examples.fft.Complex, a7: stagium.examples.fft.Complex, a8: stagium.examples.fft.Complex) => {
val x17: stagium.examples.fft.Complex = a6 * stagium.examples.fft.Complex(1.0, 0.0)
val x0: stagium.examples.fft.Complex = a1 / 1.0
val x4: stagium.examples.fft.Complex = a3 / 1.0
val x20: stagium.examples.fft.Complex = a4 / 1.0
val x1: stagium.examples.fft.Complex = a5 * stagium.examples.fft.Complex(1.0, 0.0)
val x5: stagium.examples.fft.Complex = a7 * stagium.examples.fft.Complex(1.0, 0.0)
val x21: stagium.examples.fft.Complex = a8 * stagium.examples.fft.Complex(1.0, 0.0)
val x16: stagium.examples.fft.Complex = a2 / 1.0
val x6: stagium.examples.fft.Complex = x4 + x5
val x7: stagium.examples.fft.Complex = x4 - x5
val x3: stagium.examples.fft.Complex = x0 - x1
val x19: stagium.examples.fft.Complex = x16 - x17
val x23: stagium.examples.fft.Complex = x20 - x21
val x18: stagium.examples.fft.Complex = x16 + x17
val x2: stagium.examples.fft.Complex = x0 + x1
val x22: stagium.examples.fft.Complex = x20 + x21
val x24: stagium.examples.fft.Complex = x18 / 1.0
val x13: stagium.examples.fft.Complex = x7 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x12: stagium.examples.fft.Complex = x3 / 1.0
val x8: stagium.examples.fft.Complex = x2 / 1.0
val x9: stagium.examples.fft.Complex = x6 * stagium.examples.fft.Complex(1.0, 0.0)
val x28: stagium.examples.fft.Complex = x19 / 1.0
val x29: stagium.examples.fft.Complex = x23 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x25: stagium.examples.fft.Complex = x22 * stagium.examples.fft.Complex(1.0, 0.0)
val x14: stagium.examples.fft.Complex = x12 + x13
val x10: stagium.examples.fft.Complex = x8 + x9
val x27: stagium.examples.fft.Complex = x24 - x25
val x11: stagium.examples.fft.Complex = x8 - x9
val x15: stagium.examples.fft.Complex = x12 - x13
val x26: stagium.examples.fft.Complex = x24 + x25
val x31: stagium.examples.fft.Complex = x28 - x29
val x30: stagium.examples.fft.Complex = x28 + x29
val x32: stagium.examples.fft.Complex = x10 / 1.0
val x45: stagium.examples.fft.Complex = x31 * stagium.examples.fft.Complex(-0.7071067811865475, 0.7071067811865476)
val x33: stagium.examples.fft.Complex = x26 * stagium.examples.fft.Complex(1.0, 0.0)
val x40: stagium.examples.fft.Complex = x11 / 1.0
val x44: stagium.examples.fft.Complex = x15 / 1.0
val x37: stagium.examples.fft.Complex = x30 * stagium.examples.fft.Complex(0.7071067811865476, 0.7071067811865475)
val x41: stagium.examples.fft.Complex = x27 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x36: stagium.examples.fft.Complex = x14 / 1.0
val x47: stagium.examples.fft.Complex = x44 - x45
val x42: stagium.examples.fft.Complex = x40 + x41
val x46: stagium.examples.fft.Complex = x44 + x45
val x39: stagium.examples.fft.Complex = x36 - x37
val x35: stagium.examples.fft.Complex = x32 - x33
val x38: stagium.examples.fft.Complex = x36 + x37
val x34: stagium.examples.fft.Complex = x32 + x33
val x43: stagium.examples.fft.Complex = x40 - x41
val x52: stagium.examples.fft.Complex = x42 / 2.0
val x69: stagium.examples.fft.Complex = x47 * stagium.examples.fft.Complex(0.5, -0.0)
val x48: stagium.examples.fft.Complex = x34 / 2.0
val x53: stagium.examples.fft.Complex = x43 * stagium.examples.fft.Complex(0.5, -0.0)
val x64: stagium.examples.fft.Complex = x38 / 2.0
val x65: stagium.examples.fft.Complex = x39 * stagium.examples.fft.Complex(0.5, -0.0)
val x68: stagium.examples.fft.Complex = x46 / 2.0
val x49: stagium.examples.fft.Complex = x35 * stagium.examples.fft.Complex(0.5, -0.0)
val x66: stagium.examples.fft.Complex = x64 + x65
val x70: stagium.examples.fft.Complex = x68 + x69
val x54: stagium.examples.fft.Complex = x52 + x53
val x50: stagium.examples.fft.Complex = x48 + x49
val x73: stagium.examples.fft.Complex = x70 * stagium.examples.fft.Complex(0.5, -0.0)
val x56: stagium.examples.fft.Complex = x50 / 2.0
val x57: stagium.examples.fft.Complex = x54 * stagium.examples.fft.Complex(0.5, -0.0)
val x72: stagium.examples.fft.Complex = x66 / 2.0
val x58: stagium.examples.fft.Complex = x56 + x57
val x74: stagium.examples.fft.Complex = x72 + x73
val x81: stagium.examples.fft.Complex = x74 * stagium.examples.fft.Complex(0.5, -0.0)
val x80: stagium.examples.fft.Complex = x58 / 2.0
val x82: stagium.examples.fft.Complex = x80 + x81
x82: stagium.examples.fft.Complex
} // end of code block of 69 instructions
x96: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
} // end of function x96: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
*********************************
<function8 called>Wow, just by un-staging two parameters we reduced the example from 164 instructions to just 69! Cool. But looking at the code, we see many divisions by 1.0. Let us take care of those:
def infix_/(t1: Exp[Complex], t2: Exp[Double]): Exp[Complex] =
(t1, t2) match {
case (t1, Con(1.0)) => t1
case _ => Div(t1, t2)
}
Running again, we get:
$ st-scalac fft.scala && st-scala stagium.examples.fft.Test
Need to compile and run:
*********************************
{
val x84: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex =
(a1: stagium.examples.fft.Complex, a2: stagium.examples.fft.Complex, a3: stagium.examples.fft.Complex, a4: stagium.examples.fft.Complex, a5: stagium.examples.fft.Complex, a6: stagium.examples.fft.Complex, a7: stagium.examples.fft.Complex, a8: stagium.examples.fft.Complex) => {
val x0: stagium.examples.fft.Complex = a5 * stagium.examples.fft.Complex(1.0, 0.0)
val x12: stagium.examples.fft.Complex = a6 * stagium.examples.fft.Complex(1.0, 0.0)
val x3: stagium.examples.fft.Complex = a7 * stagium.examples.fft.Complex(1.0, 0.0)
val x15: stagium.examples.fft.Complex = a8 * stagium.examples.fft.Complex(1.0, 0.0)
val x14: stagium.examples.fft.Complex = a2 - x12
val x17: stagium.examples.fft.Complex = a4 - x15
val x4: stagium.examples.fft.Complex = a3 + x3
val x1: stagium.examples.fft.Complex = a1 + x0
val x13: stagium.examples.fft.Complex = a2 + x12
val x5: stagium.examples.fft.Complex = a3 - x3
val x16: stagium.examples.fft.Complex = a4 + x15
val x2: stagium.examples.fft.Complex = a1 - x0
val x6: stagium.examples.fft.Complex = x4 * stagium.examples.fft.Complex(1.0, 0.0)
val x9: stagium.examples.fft.Complex = x5 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x21: stagium.examples.fft.Complex = x17 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x18: stagium.examples.fft.Complex = x16 * stagium.examples.fft.Complex(1.0, 0.0)
val x10: stagium.examples.fft.Complex = x2 + x9
val x20: stagium.examples.fft.Complex = x13 - x18
val x7: stagium.examples.fft.Complex = x1 + x6
val x11: stagium.examples.fft.Complex = x2 - x9
val x19: stagium.examples.fft.Complex = x13 + x18
val x23: stagium.examples.fft.Complex = x14 - x21
val x8: stagium.examples.fft.Complex = x1 - x6
val x22: stagium.examples.fft.Complex = x14 + x21
val x24: stagium.examples.fft.Complex = x19 * stagium.examples.fft.Complex(1.0, 0.0)
val x27: stagium.examples.fft.Complex = x22 * stagium.examples.fft.Complex(0.7071067811865476, 0.7071067811865475)
val x33: stagium.examples.fft.Complex = x23 * stagium.examples.fft.Complex(-0.7071067811865475, 0.7071067811865476)
val x30: stagium.examples.fft.Complex = x20 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x35: stagium.examples.fft.Complex = x11 - x33
val x32: stagium.examples.fft.Complex = x8 - x30
val x28: stagium.examples.fft.Complex = x10 + x27
val x26: stagium.examples.fft.Complex = x7 - x24
val x31: stagium.examples.fft.Complex = x8 + x30
val x34: stagium.examples.fft.Complex = x11 + x33
val x29: stagium.examples.fft.Complex = x10 - x27
val x25: stagium.examples.fft.Complex = x7 + x24
val x52: stagium.examples.fft.Complex = x28 / 2.0
val x56: stagium.examples.fft.Complex = x34 / 2.0
val x53: stagium.examples.fft.Complex = x29 * stagium.examples.fft.Complex(0.5, -0.0)
val x40: stagium.examples.fft.Complex = x31 / 2.0
val x57: stagium.examples.fft.Complex = x35 * stagium.examples.fft.Complex(0.5, -0.0)
val x37: stagium.examples.fft.Complex = x26 * stagium.examples.fft.Complex(0.5, -0.0)
val x41: stagium.examples.fft.Complex = x32 * stagium.examples.fft.Complex(0.5, -0.0)
val x36: stagium.examples.fft.Complex = x25 / 2.0
val x42: stagium.examples.fft.Complex = x40 + x41
val x58: stagium.examples.fft.Complex = x56 + x57
val x38: stagium.examples.fft.Complex = x36 + x37
val x54: stagium.examples.fft.Complex = x52 + x53
val x61: stagium.examples.fft.Complex = x58 * stagium.examples.fft.Complex(0.5, -0.0)
val x60: stagium.examples.fft.Complex = x54 / 2.0
val x45: stagium.examples.fft.Complex = x42 * stagium.examples.fft.Complex(0.5, -0.0)
val x44: stagium.examples.fft.Complex = x38 / 2.0
val x46: stagium.examples.fft.Complex = x44 + x45
val x62: stagium.examples.fft.Complex = x60 + x61
val x69: stagium.examples.fft.Complex = x62 * stagium.examples.fft.Complex(0.5, -0.0)
val x68: stagium.examples.fft.Complex = x46 / 2.0
val x70: stagium.examples.fft.Complex = x68 + x69
x70: stagium.examples.fft.Complex
} // end of code block of 57 instructions
x84: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
} // end of function x84: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
*********************************
<function8 called>Down to 57 instructions. Now we see see many multiplications, either by 1 or by 0.5. We can also eliminate those:
def infix_*(t1: Exp[Complex], t2: Exp[Complex]): Exp[Complex] =
(t1, t2) match {
case (t1, Con(Complex(scalar, 0.0))) =>
if (scalar == 1.0)
t1
else
infix_**(t1, Con(scalar))
case _ => Mul(t1, t2)
}Running again we get:
$ st-scalac fft.scala && st-scala stagium.examples.fft.Test
Need to compile and run:
*********************************
{
val x77: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex =
(a1: stagium.examples.fft.Complex, a2: stagium.examples.fft.Complex, a3: stagium.examples.fft.Complex, a4: stagium.examples.fft.Complex, a5: stagium.examples.fft.Complex, a6: stagium.examples.fft.Complex, a7: stagium.examples.fft.Complex, a8: stagium.examples.fft.Complex) => {
val x10: stagium.examples.fft.Complex = a2 - a6
val x0: stagium.examples.fft.Complex = a1 + a5
val x1: stagium.examples.fft.Complex = a1 - a5
val x11: stagium.examples.fft.Complex = a4 + a8
val x12: stagium.examples.fft.Complex = a4 - a8
val x3: stagium.examples.fft.Complex = a3 - a7
val x9: stagium.examples.fft.Complex = a2 + a6
val x2: stagium.examples.fft.Complex = a3 + a7
val x14: stagium.examples.fft.Complex = x9 - x11
val x4: stagium.examples.fft.Complex = x0 + x2
val x6: stagium.examples.fft.Complex = x3 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x13: stagium.examples.fft.Complex = x9 + x11
val x5: stagium.examples.fft.Complex = x0 - x2
val x15: stagium.examples.fft.Complex = x12 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x17: stagium.examples.fft.Complex = x10 - x15
val x7: stagium.examples.fft.Complex = x1 + x6
val x19: stagium.examples.fft.Complex = x4 - x13
val x23: stagium.examples.fft.Complex = x14 * stagium.examples.fft.Complex(6.123233995736766E-17, 1.0)
val x8: stagium.examples.fft.Complex = x1 - x6
val x16: stagium.examples.fft.Complex = x10 + x15
val x18: stagium.examples.fft.Complex = x4 + x13
val x24: stagium.examples.fft.Complex = x5 + x23
val x20: stagium.examples.fft.Complex = x16 * stagium.examples.fft.Complex(0.7071067811865476, 0.7071067811865475)
val x26: stagium.examples.fft.Complex = x17 * stagium.examples.fft.Complex(-0.7071067811865475, 0.7071067811865476)
val x29: stagium.examples.fft.Complex = x18 / 2.0
val x25: stagium.examples.fft.Complex = x5 - x23
val x30: stagium.examples.fft.Complex = x19 * 0.5
val x27: stagium.examples.fft.Complex = x8 + x26
val x33: stagium.examples.fft.Complex = x24 / 2.0
val x21: stagium.examples.fft.Complex = x7 + x20
val x28: stagium.examples.fft.Complex = x8 - x26
val x31: stagium.examples.fft.Complex = x29 + x30
val x34: stagium.examples.fft.Complex = x25 * 0.5
val x22: stagium.examples.fft.Complex = x7 - x20
val x46: stagium.examples.fft.Complex = x22 * 0.5
val x35: stagium.examples.fft.Complex = x33 + x34
val x45: stagium.examples.fft.Complex = x21 / 2.0
val x37: stagium.examples.fft.Complex = x31 / 2.0
val x49: stagium.examples.fft.Complex = x27 / 2.0
val x50: stagium.examples.fft.Complex = x28 * 0.5
val x47: stagium.examples.fft.Complex = x45 + x46
val x51: stagium.examples.fft.Complex = x49 + x50
val x38: stagium.examples.fft.Complex = x35 * 0.5
val x39: stagium.examples.fft.Complex = x37 + x38
val x53: stagium.examples.fft.Complex = x47 / 2.0
val x54: stagium.examples.fft.Complex = x51 * 0.5
val x61: stagium.examples.fft.Complex = x39 / 2.0
val x55: stagium.examples.fft.Complex = x53 + x54
val x62: stagium.examples.fft.Complex = x55 * 0.5
val x63: stagium.examples.fft.Complex = x61 + x62
x63: stagium.examples.fft.Complex
} // end of code block of 50 instructions
x77: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
} // end of function x77: (stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex, stagium.examples.fft.Complex) => stagium.examples.fft.Complex
*********************************
<function8 called>So we're down to 50 instructions, from 164. Furthermore, most of these instructions are scalar multiplications, which can be further simplified. Also, since Complex is a value class, its two fields can be split and treated separately. But since these are all implemented in the lightweight modular staging framework we will stop here and conclude that using the staging plugin, not only that we were able to burn through several layers of collection functions, but we were also able to reduce the example to mere additions, subtractions, multiplications and divisions.
See the [next chapter](Test Suite) for running the test suite.