Previous: Dependency analysis, Up: Loop Analysis and Representation
11.9 Linear loop transformations framework
Lambda is a framework that allows transformations of loops using non-singular matrix based transformations of the iteration space and loop bounds. This allows compositions of skewing, scaling, interchange, and reversal transformations. These transformations are often used to improve cache behavior or remove inner loop dependencies to allow parallelization and vectorization to take place.
To perform these transformations, Lambda requires that the loopnest be
converted into a internal form that can be matrix transformed easily.
To do this conversion, the function
gcc_loopnest_to_lambda_loopnest is provided. If the loop cannot
be transformed using lambda, this function will return NULL.
Once a lambda_loopnest is obtained from the conversion function,
it can be transformed by using lambda_loopnest_transform, which
takes a transformation matrix to apply. Note that it is up to the
caller to verify that the transformation matrix is legal to apply to the
loop (dependence respecting, etc). Lambda simply applies whatever
matrix it is told to provide. It can be extended to make legal matrices
out of any non-singular matrix, but this is not currently implemented.
Legality of a matrix for a given loopnest can be verified using
lambda_transform_legal_p.
Given a transformed loopnest, conversion back into gcc IR is done by
lambda_loopnest_to_gcc_loopnest. This function will modify the
loops so that they match the transformed loopnest.