at.dms.kjc.sir.linear.frequency
Class LEETFrequencyReplacer

java.lang.Object
  at.dms.kjc.sir.EmptyStreamVisitor
      at.dms.kjc.sir.linear.LinearReplacer
          at.dms.kjc.sir.linear.frequency.FrequencyReplacer
              at.dms.kjc.sir.linear.frequency.LEETFrequencyReplacer

All Implemented Interfaces:

Constants, StreamVisitor

public class LEETFrequencyReplacer
extends FrequencyReplacer

Replaces linear filters of sufficient length with a conversion into the frequency domain, multiplication, and convert the product back into the time domain. In so doing, this also increases the peek, pop and push rates to take advantage of the frequency transformation.
$Id: LEETFrequencyReplacer.java,v 1.25 2006/06/14 20:36:19 thies Exp $

Field Summary

static boolean

didTransform Indicates whether or not anything has been transformed to the frequency domain.

Fields inherited from interface at.dms.kjc.Constants

CMP_VERSION, JAV_CLASS, JAV_CLONE, JAV_CLONEABLE, JAV_CONSTRUCTOR, JAV_ERROR, JAV_EXCEPTION, JAV_INIT, JAV_LENGTH, JAV_NAME_SEPARATOR, JAV_OBJECT, JAV_OUTER_THIS, JAV_RUNTIME, JAV_RUNTIME_EXCEPTION, JAV_STATIC_INIT, JAV_STRING, JAV_STRINGBUFFER, JAV_THIS, JAV_THROWABLE, OPE_BAND, OPE_BNOT, OPE_BOR, OPE_BSR, OPE_BXOR, OPE_EQ, OPE_GE, OPE_GT, OPE_LE, OPE_LNOT, OPE_LT, OPE_MINUS, OPE_NE, OPE_PERCENT, OPE_PLUS, OPE_POSTDEC, OPE_POSTINC, OPE_PREDEC, OPE_PREINC, OPE_SIMPLE, OPE_SL, OPE_SLASH, OPE_SR, OPE_STAR, TID_ARRAY, TID_BIT, TID_BOOLEAN, TID_BYTE, TID_CHAR, TID_CLASS, TID_DOUBLE, TID_FLOAT, TID_INT, TID_LONG, TID_SHORT, TID_VECTOR, TID_VOID, VECTOR_EMPTY

Fields inherited from interface at.dms.classfile.Constants

ACC_ABSTRACT, ACC_FINAL, ACC_INLINE, ACC_INTERFACE, ACC_NATIVE, ACC_PRIVATE, ACC_PROTECTED, ACC_PUBLIC, ACC_STATIC, ACC_STRICT, ACC_SUPER, ACC_SYNCHRONIZED, ACC_TRANSIENT, ACC_VOLATILE, ATT_CODE, ATT_CONSTANTVALUE, ATT_DEPRECATED, ATT_EXCEPTIONS, ATT_GENERIC, ATT_INNERCLASSES, ATT_LINENUMBERTABLE, ATT_LOCALVARIABLETABLE, ATT_SOURCEFILE, ATT_SYNTHETIC, CST_CLASS, CST_DOUBLE, CST_FIELD, CST_FLOAT, CST_INTEGER, CST_INTERFACEMETHOD, CST_LONG, CST_METHOD, CST_NAMEANDTYPE, CST_STRING, CST_UTF8, ENV_DEBUG_MODE, ENV_USE_CACHE, JAVA_MAGIC, JAVA_MAJOR, JAVA_MINOR, MAX_CODE_PER_METHOD, opc_aaload, opc_aastore, opc_aconst_null, opc_aload, opc_aload_0, opc_aload_1, opc_aload_2, opc_aload_3, opc_anewarray, opc_areturn, opc_arraylength, opc_astore, opc_astore_0, opc_astore_1, opc_astore_2, opc_astore_3, opc_athrow, opc_baload, opc_bastore, opc_bipush, opc_caload, opc_castore, opc_checkcast, opc_d2f, opc_d2i, opc_d2l, opc_dadd, opc_daload, opc_dastore, opc_dcmpg, opc_dcmpl, opc_dconst_0, opc_dconst_1, opc_ddiv, opc_dload, opc_dload_0, opc_dload_1, opc_dload_2, opc_dload_3, opc_dmul, opc_dneg, opc_drem, opc_dreturn, opc_dstore, opc_dstore_0, opc_dstore_1, opc_dstore_2, opc_dstore_3, opc_dsub, opc_dup, opc_dup_x1, opc_dup_x2, opc_dup2, opc_dup2_x1, opc_dup2_x2, opc_f2d, opc_f2i, opc_f2l, opc_fadd, opc_faload, opc_fastore, opc_fcmpg, opc_fcmpl, opc_fconst_0, opc_fconst_1, opc_fconst_2, opc_fdiv, opc_fload, opc_fload_0, opc_fload_1, opc_fload_2, opc_fload_3, opc_fmul, opc_fneg, opc_frem, opc_freturn, opc_fstore, opc_fstore_0, opc_fstore_1, opc_fstore_2, opc_fstore_3, opc_fsub, opc_getfield, opc_getstatic, opc_goto, opc_goto_w, opc_i2b, opc_i2c, opc_i2d, opc_i2f, opc_i2l, opc_i2s, opc_iadd, opc_iaload, opc_iand, opc_iastore, opc_iconst_0, opc_iconst_1, opc_iconst_2, opc_iconst_3, opc_iconst_4, opc_iconst_5, opc_iconst_m1, opc_idiv, opc_if_acmpeq, opc_if_acmpne, opc_if_icmpeq, opc_if_icmpge, opc_if_icmpgt, opc_if_icmple, opc_if_icmplt, opc_if_icmpne, opc_ifeq, opc_ifge, opc_ifgt, opc_ifle, opc_iflt, opc_ifne, opc_ifnonnull, opc_ifnull, opc_iinc, opc_iload, opc_iload_0, opc_iload_1, opc_iload_2, opc_iload_3, opc_imul, opc_ineg, opc_instanceof, opc_invokeinterface, opc_invokespecial, opc_invokestatic, opc_invokevirtual, opc_ior, opc_irem, opc_ireturn, opc_ishl, opc_ishr, opc_istore, opc_istore_0, opc_istore_1, opc_istore_2, opc_istore_3, opc_isub, opc_iushr, opc_ixor, opc_jsr, opc_jsr_w, opc_l2d, opc_l2f, opc_l2i, opc_ladd, opc_laload, opc_land, opc_lastore, opc_lcmp, opc_lconst_0, opc_lconst_1, opc_ldc, opc_ldc_w, opc_ldc2_w, opc_ldiv, opc_lload, opc_lload_0, opc_lload_1, opc_lload_2, opc_lload_3, opc_lmul, opc_lneg, opc_lookupswitch, opc_lor, opc_lrem, opc_lreturn, opc_lshl, opc_lshr, opc_lstore, opc_lstore_0, opc_lstore_1, opc_lstore_2, opc_lstore_3, opc_lsub, opc_lushr, opc_lxor, opc_monitorenter, opc_monitorexit, opc_multianewarray, opc_new, opc_newarray, opc_nop, opc_pop, opc_pop2, opc_putfield, opc_putstatic, opc_ret, opc_return, opc_saload, opc_sastore, opc_sipush, opc_swap, opc_tableswitch, opc_wide, opc_xxxunusedxxx, POO_ASCII_CONSTANT, POO_CLASS_CONSTANT, POO_DOUBLE_CONSTANT, POO_FLOAT_CONSTANT, POO_INTEGER_CONSTANT, POO_LONG_CONSTANT, POO_NAT_CONSTANT, POO_REF_CONSTANT, POO_STRING_CONSTANT, TYP_ADDRESS, TYP_DOUBLE, TYP_FLOAT, TYP_INT, TYP_LONG, TYP_REFERENCE, TYP_VOID

Method Summary

static int	calculateN(int x) calculates the appropriate size FFT to perform.
static boolean	canReplace(SIRStream str, LinearAnalyzer lfa) Returns whether or not we can replace with this replacer.
float[]	getRealArray(LinearFilterRepresentation filterRep, int col, int size) Returns an array of floating point numbers that correspond to the real part of the FIR filter's weights.
JStatement	makeArrayAddAndPushStatement(JLocalVariable arr1, JLocalVariable arr2, JVariableDefinition indexVar) makes an array push statement of the following form: push(this.arr1[indexVar] + this.arr2[indexVar]);
JStatement	makeArrayAssignment(JLocalVariable field, int index, float value) Creates an assignment expression of the form: this.f[index]=value;
JStatement	makeArrayAssignment(JLocalVariable field, JExpression index, JExpression assignedValue, String comment) Creates an assignment expression of the form: this.f[index]=rhs;
JStatement	makeArrayAssignment(JLocalVariable field, JVariableDefinition index, JExpression assignedValue, String comment) Creates an assignment expression of the form: this.f[index]=rhs;
JStatement	makeArrayPushStatement(JLocalVariable arr, JVariableDefinition indexVar)
JStatement	makeConstantForLoop(JVariableDefinition loopVar, int initVal, int maxVal, JStatement forBody) Generates the a for loop of the form:
static SIRFilter	makeDecimatorForFrequencyNode(int freqPush, int freqPop, CType type) Returns a filter that has this behavior:
JStatement	makeFrequencyScale(JVariableDefinition fieldToScale, int filterSize) An assignment to scale each element in an array by 1/size via a callout.
JMethodDeclaration	makeNewInit(LinearFilterRepresentation linearRep, JVariableDefinition[] weightFields, JVariableDefinition[] partialFields, JVariableDefinition inputBufferField, JVariableDefinition tempBufferField, JVariableDefinition[] outputBufferFields, int filterSize, int x) Make the init function.
JMethodDeclaration	makeNewWork(int functionType, JVariableDefinition[] weightFields, JVariableDefinition[] partialFields, JVariableDefinition inputBufferField, JVariableDefinition tempBufferField, JVariableDefinition[] outputBufferFields, int filterSize, int x, int N) Make both the initWork and the work function (because they are not very different). We make a function that copies N+2(x-1) elements from the input tape into a local array, calls the library function with the local array and the weight field to calcluate the FFT of the input and the weight fields.
JStatement	makePartialCopyExpression(JLocalVariable field1, JExpression index1, JLocalVariable field2, JExpression index2) Makes a copy expression from one array field to another array field of the form this.field1[index1] = this.field2[index2].
void	makePopStatements(JBlock body, int n) adds n popFloat() statements to the end of body.
boolean	makeReplacement(SIRStream self) Does the actual work of replacing something that computes a convolution sum with something that does a FFT, multiply, and then IFFT.
JStatement	makeTimeToFrequencyConversion(JVariableDefinition fieldToConvert, int filterSize) An assignment to convert a field to frequency, via an external callout.
JVariableDefinition	makeWeightField(String name, int arrayLength) Create the field that we put the filter's frequency response in.

Methods inherited from class at.dms.kjc.sir.linear.frequency.FrequencyReplacer

doReplace

Methods inherited from class at.dms.kjc.sir.linear.LinearReplacer

appendFieldDeclaration, appendFieldDeclarations, getArrayType, makeArrayFieldAccessExpr, makeArrayFieldAccessExpr, makeArrayFieldAccessExpr, makeAssignmentStatement, makeComment, makeFieldAccessExpression, makeFieldInitialization, makeIncrementStatement, makeLessThanExpression, makeLocalVarExpression, preVisitFeedbackLoop, preVisitPipeline, preVisitSplitJoin, visitFilter

Methods inherited from class at.dms.kjc.sir.EmptyStreamVisitor

postVisitFeedbackLoop, postVisitPipeline, postVisitSplitJoin, postVisitStream, preVisitStream, visitPhasedFilter

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

didTransform

public static boolean didTransform

Indicates whether or not anything has been transformed to the frequency domain. This can be used to indicate whether or not the final executable needs to link against an FFT library.

Method Detail

canReplace

public static boolean canReplace(SIRStream str,
                                 LinearAnalyzer lfa)

Returns whether or not we can replace with this replacer. This ensures that our assumptions are met.

makeReplacement

public boolean makeReplacement(SIRStream self)

Does the actual work of replacing something that computes a convolution sum with something that does a FFT, multiply, and then IFFT.

Specified by:

makeReplacement in class LinearReplacer

makeDecimatorForFrequencyNode

public static SIRFilter makeDecimatorForFrequencyNode(int freqPush,
                                                      int freqPop,
                                                      CType type)

Returns a filter that has this behavior:

   for (int i=0; i<freqPush; i++) { push(pop()) }
   for (int i=0; i<freqPush; i++) { for (int j=0;j<freqPop-1; j++) { pop() } }
 

Will return a filter with a null parent. This is intended to follow a frequency node that has a pop rate more than one; the freqPush and freqPop refers to the push and pop rates of the frequency node.

makeWeightField

public JVariableDefinition makeWeightField(String name,
                                           int arrayLength)

Create the field that we put the filter's frequency response in. The field is an array of floats, and we will have one array for the real part of the repsonse and one array for the imaginary part of the response.

makeNewInit

public JMethodDeclaration makeNewInit(LinearFilterRepresentation linearRep,
                                      JVariableDefinition[] weightFields,
                                      JVariableDefinition[] partialFields,
                                      JVariableDefinition inputBufferField,
                                      JVariableDefinition tempBufferField,
                                      JVariableDefinition[] outputBufferFields,
                                      int filterSize,
                                      int x)

Make the init function. The init function allocates space for the various fields (frequency weight fields are of size filterSize, and partial result fields are of size x-1) and calculates the FFT of the impulse response and stores it in the weight fields.

makeTimeToFrequencyConversion

public JStatement makeTimeToFrequencyConversion(JVariableDefinition fieldToConvert,
                                                int filterSize)

An assignment to convert a field to frequency, via an external callout.

makeFrequencyScale

public JStatement makeFrequencyScale(JVariableDefinition fieldToScale,
                                     int filterSize)

An assignment to scale each element in an array by 1/size via a callout.

makeArrayAssignment

public JStatement makeArrayAssignment(JLocalVariable field,
                                      int index,
                                      float value)

Creates an assignment expression of the form: this.f[index]=value;

makeArrayAssignment

public JStatement makeArrayAssignment(JLocalVariable field,
                                      JVariableDefinition index,
                                      JExpression assignedValue,
                                      String comment)

Creates an assignment expression of the form: this.f[index]=rhs;

makeArrayAssignment

public JStatement makeArrayAssignment(JLocalVariable field,
                                      JExpression index,
                                      JExpression assignedValue,
                                      String comment)

Creates an assignment expression of the form: this.f[index]=rhs;

makeNewWork

public JMethodDeclaration makeNewWork(int functionType,
                                      JVariableDefinition[] weightFields,
                                      JVariableDefinition[] partialFields,
                                      JVariableDefinition inputBufferField,
                                      JVariableDefinition tempBufferField,
                                      JVariableDefinition[] outputBufferFields,
                                      int filterSize,
                                      int x,
                                      int N)

Make both the initWork and the work function (because they are not very different).
We make a function that copies N+2(x-1) elements from the input tape into a local array, calls the library function with the local array and the weight field to calcluate the FFT of the input and the weight fields. If we are making the initWork function, then just the middle N elements of the result are pushed and if we are making the work function then the x-1 partials are added to the first x-1 elements of the results and we push out the first N+x-1 elements. For both types of work we then save the last x-1 elements of the DFT output in the partial results fields for the next execution. Note that filterSize = N + 2(x-1).
If the GENFORLOOPS flag is set, then we will actually generate for loops in the work function rather than generating unrolled code.

makePartialCopyExpression

public JStatement makePartialCopyExpression(JLocalVariable field1,
                                            JExpression index1,
                                            JLocalVariable field2,
                                            JExpression index2)

Makes a copy expression from one array field to another array field of the form this.field1[index1] = this.field2[index2].

makePopStatements

public void makePopStatements(JBlock body,
                              int n)

adds n popFloat() statements to the end of body.

makeArrayAddAndPushStatement

public JStatement makeArrayAddAndPushStatement(JLocalVariable arr1,
                                               JLocalVariable arr2,
                                               JVariableDefinition indexVar)

makes an array push statement of the following form: push(this.arr1[indexVar] + this.arr2[indexVar]);

makeArrayPushStatement

public JStatement makeArrayPushStatement(JLocalVariable arr,
                                         JVariableDefinition indexVar)

getRealArray

public float[] getRealArray(LinearFilterRepresentation filterRep,
                            int col,
                            int size)

Returns an array of floating point numbers that correspond to the real part of the FIR filter's weights. Size is the size of the array to allocate. This might need to be bigger than the actual number of elements in the FIR response because we will be taking and FFT of the data.
Col represents which column of data we want to get the coefficients from. This is the column index in the actual filter's matrix rep.

makeConstantForLoop

public JStatement makeConstantForLoop(JVariableDefinition loopVar,
                                      int initVal,
                                      int maxVal,
                                      JStatement forBody)

Generates the a for loop of the form:

 for(loopVar = initVal; loopVar<maxVal; loopVar++) {loopBody}
 

calculateN

public static int calculateN(int x)

calculates the appropriate size FFT to perform. It is passed x, the length of the impuse response of the filter, and it returns the actual N, the number of output points that will be produced by one execution of the filter.
This implementation works by calculating a targetN that is a multiple of x, and then scaling up to the next power of two.