Compiler optimization for complex exponential calculations

A computing device to optimize a source program, the computing device comprising:

• a processor;
• source code having a code segment including a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index;
• and
• a memory having a compiler stored therein, wherein the compiler (i) a loop detect module to detect the code segment, (ii) a loop optimize module to optimize the code segment in response to detection of the code segment, and (iii) a code generator module to generate output code as a function of the optimized code segment, wherein the loop optimize module to:
• tile the loop to generate an outer loop having a second number of iterations and a nested inner loop having a third number of iterations;
• generate code to calculate a first coefficient array having a number of elements equal to the third number of iterations, wherein each element of the first coefficient array equals an exponential function of the loop-invariant complex number multiplied by a first coefficient array index;
• generate code to calculate a second coefficient array having a number of elements equal to the second number of iterations, wherein each element of the second coefficient array equals an exponential function of the loop-invariant complex number multiplied by the third number of iterations and a second coefficient array index;
• and
• replace the exponential function call with a multiplicative expression of an element of the first coefficient array at an inner loop index multiplied by an element of the second coefficient array at an outer loop index.

A method for optimizing a source program on a computing device comprising a processor and a memory, the method comprising:

• detecting, by a compiler of the computing device, a code segment of the source program having a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index;
• and
• optimizing, by the compiler, the code segment to generate an optimized code segment in response to detecting the code segment, wherein optimizing the code segment comprises:
• (i) tiling the loop to generate an outer loop having a second number of iterations and a nested inner loop having a third number of iterations;
• (ii) generating code to calculate the first coefficient array having a number of elements equal to the third number of iterations, wherein each element of the first coefficient array equals the exponential function of the loop-invariant complex number multiplied by the first coefficient array index;
• (iii) generating code to calculate the second coefficient array having a number of elements equal to the second number of iterations, wherein each element of the second coefficient array equals the exponential function of the loop-invariant complex number multiplied by the third number of iterations and the second coefficient array index;
• (iv) replacing the exponential function call with a multiplicative expression of an element of the first coefficient array at an inner loop index multiplied by an element of the second coefficient array at an outer loop index.

One or more non-transitory, machine readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to:

• detect, by a compiler, a code segment of a source program having a loop, the loop having a first number of iterations and including an exponential function call having an argument including a loop-invariant complex number multiplied by a loop index;
• and
• optimize, by the compiler, the code segment to generate an optimized code segment in response to detecting the code segment, wherein to optimize the code segment comprises to:
• (i) tile the loop to generate an outer loop having a second number of iterations and a nested inner loop having a third number of iterations;
• (ii) generate code to calculate a first coefficient array having a number of elements equal to the third number of iterations, wherein each element of the first coefficient array equals an exponential function of the loop-invariant complex number multiplied by the first coefficient array index;
• (iii) generate code to calculate a second coefficient array having a number of elements equal to the second number of iterations, wherein each element of the second coefficient array equals an exponential function of the loop-invariant complex number multiplied by the third number of iterations and the second coefficient array index;
• and
• (iv) replace the exponential function call with a multiplicative expression of an element of the first coefficient array at an inner loop index multiplied by an element of the second coefficient array at an outer loop index.