Dependence Testing
Scale uses the Omega Test by W.Pugh for array dependence testing.
Scale can build dependence and locality graphs for both the Clef AST and Scribble CFG representations.
The Scribble CFG graphs are used and updated by the loop transformations which rely on the data dependence information.
Loop Induction Variables
Scale computes the set of candidate induction variables and constructs the directed graph:
there is an edge between candidates T and U if T is used to compute U.
Each connected component in the graph forms an induction set.
Loop Transformation
Scale performs the following loop transformations:
- Loop interchange (works for simple programs)
- Strip mining (in progress)
- Loop tiling (in progress)
- Loop distribution (in progress)
- Loop unrolling (in progress)
- Loop fusion (in progress)
To be applied, each transformation must be:
- applicable (it can be performed mechanically)
- safe (it preserves the meaning of the original program)
i.e., it does not violate dependencies
- profitable (it improves the cost of a program based on a cost model)
Return to Scale home page.
(Last changed: March 21, 2007.)