SCC

SCC's are a powerful representation for summarization of dependencies.

Class hierarchy

NOELLE categorizes SCC with a class hierarchy. This hierarchy solely designed to categorize SCC arising from loops. Only leaves of the inheritance tree can be instantiated (e.g. LoopCarriedUnknownSCC). An SCC will belong to the category that would lead with the lowest overhead.

The hierarchy can be explored through the Visitor Pattern. In the following A,B → C means A and B are children of C.

Classes marked with * are not yet implemented.

LoopCarriedSCC → GenericSCC

Any SCC with at least one loop-carried dependence falls into this category.

LoopCarriedUnknownSCC → LoopCarriedSCC

All SCCs that cannot be categorized in any of the other classes fall into this class. No further analyses or transformations are available for this kind of SCC.

LoopIterationSCC → GenericSCC

Some dependencies are present but are limited to a single iteration.

ReductionSCC → LoopCarriedSCC

The presence of a reduction is guaranteed.

VariableReductionSCC, ObjectReductionSCC → ReductionSCC

These two categories handle variables or objects that get privatized during a reduction.

VariableBinaryReductionSCC, VariableFunctionReductionSCC → VariableReductionSCC

Any reduction operated by a binary function or a generic user-defined function that cannot be proven to be binary. Both functions have to operate solely on variables.

ObjectBinaryReductionSCC, ObjectFunctionReductionSCC → ObjectReductionSCC

Any reduction operated by a binary function or a generic user-defined function that cannot be proven to be binary. Both functions have to operate solely on objects that are not variables.

RecomputableSCC → LoopCarriedSCC

Used when values produced by the SCC are recomputable, e.g. induction variables.

UnknownClosedFormSCC → RecomputableSCC

Used when an SCC is recomputable in a finite number of recursive steps. For example, an arithmetic operation that cannot be proven to be linear or polynomial.

KnownClosedFormSCC → RecomputableSCC

Used when an SCC is recomputable in a single constant-time step.

SingleAccumulatorRecomputableSCC → KnownClosedFormSCC

Used for any known-closed-form recomputable SCC that involves a single phi instruction.

MultipleAccumulatorRecomputableSCC* → KnownClosedFormSCC

Used for any known-closed-form recomputable SCC that involves more than one phi instruction.

InductionVariableSCC → SingleAccumulatorRecomputableSCC

Used for a generic induction variable.

LinearInductionVariable, PolyInductionVariable* → InductionVariableSCC

These specializations are used when an induction variable is linear or is polynomial but not linear, respectively.

WrapUpVariableSCC*, FlipFlopVariableSCC* → SingleAccumulatorRecomputableSCC

These categories handle induction variables as described in the paper Beyond Induction Variables by Michael Wolfe.

MemoryClonableSCC → LoopCarriedSCC

Related to an object that can be safely cloned.

StackObjectClonableSCC, HeapObjectClonable*, GlobalObjectClonable* → MemoryClonableSCC

Specializations for clonable stack, heap and global objects respectively.

OutputFileSCC → LoopCarriedSCC

Something like you have a printf that we can prove is gonna use the same buffer.

OutputFileSCC → LoopCarriedSCC

E.g. a call to printf that is guaranteed to use the same buffer.