at.dms.kjc.sir.lowering
Class Vectorizable

java.lang.Object
  at.dms.kjc.sir.lowering.Vectorizable

public class Vectorizable
extends Object

Determine if code is naively vectorizable by interleaving executions of different steady states.
$Id$
Invoked from vectorizeEnable and from fusePipelinesOfVectorizableFilters There should be no need to call methods in this class elsewhere.

Author:

Allyn Dimock

Constructor Summary

Vectorizable()

Method Summary

static boolean	hasSideEffects(SIRFilter f) Check whether a filter has side effects (I/O).
static boolean	isDataDependent(SIRFilter f) Check whether a filter's behavior is data dependent (other than through fields).
static boolean	isUseful(SIRStream str) Determine whether a vectorizable stream may contain useful vector operations.
static boolean	vectorizable(SIRFilter f) Check whether a filter could be naively vectorized by interleaving executions of different steady states.
static Set<SIRFilter>	vectorizableStr(SIRStream str) Return set of naively vectorizable filters in stream.

Methods inherited from class java.lang.Object

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

Constructor Detail

Vectorizable

public Vectorizable()

Method Detail

vectorizableStr

public static Set<SIRFilter> vectorizableStr(SIRStream str)

Return set of naively vectorizable filters in stream. See vectorizable for what makes a filter naively vectorizable.

Parameters:

str - Stream to check

Returns:

Set of filters passing vectorizable test

vectorizable

public static boolean vectorizable(SIRFilter f)

Check whether a filter could be naively vectorized by interleaving executions of different steady states. (Does not answer question as to whether it is profitable to do so.)
A filter is naively vectorizable if:

• Its input type or its output type is a 32-bit int or float.
• It has no loop-carried dependencies between steady states.
• It has no visible side effects.
• It has no data-dependent branches. (This should also preclude dynamic-rate filters.)
• It is not a descendant of a feedbackloop: This restriction can be lifted with a bit of work: the problem is that vectorization changes the multiplicity of a filter, if this multiplicity change propagates back to the top of a body (or loop) construct then the multiplicity must also change in the corresponding loop (or body). Furthermore, the number of enqueued values will be insufficient, which means that we need to clone non-vectorized versions to become part of pre-work functions in the body and loop.
• It is not a message sender or a message receiver.

TODO: Should allow filters with void input type to be vectorizable if the values being constructed for the output do not participate in conditionals or array offset calculations and the filter has no loop-carried dependencies of side effects. Such filters should only be vectorizable if the following filter is also vectorizable: else adds overhead. To do this would require extra work and is probably only of use in cases where a source dumps out the contents of a static array (tde_pp, gmti).

Parameters:

f - : a filter to check.

Returns:

true if there are no local conditions precluding vectorizing the filter.

hasSideEffects

public static boolean hasSideEffects(SIRFilter f)

Check whether a filter has side effects (I/O). This includes message send and receive.

Parameters:

f - : a filter to check

Returns:

true if no side effects, and no messages.

isDataDependent

public static boolean isDataDependent(SIRFilter f)

Check whether a filter's behavior is data dependent (other than through fields). (A peek or pop flows to a branch condition, array offset, or peek offset.)

   
 push(arr[pop()]);
 foo = pop();  bar = peek(foo);
 foo = peek(5); if (foo > 0) baz++;
 

You can check as to whether there is any possibility of a loop-carried dependency through fields by checking that (! StatelessDuplicate.hasMutableState(f)). Currently flow insensitive, context insensitive. Used without need for object state to check id a filter is data dependent. Is used, with need for object state, to determine number of vectorizable artihmetic ops in a vectorizable filter.

Parameters:

f - : a filter to check.

Returns:

true if no data-dependent branches or offsets.

isUseful

public static boolean isUseful(SIRStream str)

Determine whether a vectorizable stream may contain useful vector operations. Approximates as to whether a vectorizable stream contains sufficient vector arithmetic operations. Currently says that any stream other than an identity filter or a collapsed splitter or collapsed joiner is useful. This keeps a few of filters that are known to degrade in performance when vectorized in isolation (but not necessarily when vectorized in conjuncrion with surrounding filters) from being vectorized.

Parameters:

str - the SIRStream to check, in which all filters are vectorizable.

Returns:

true if we should vectorise the passed stream.