Outer loop vectorization

Claim 1

A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of: analyzing each iterative loop to determine if it is vectorizable, wherein the step of analyzing each iterative loop includes the steps of: preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; and extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein each level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level; determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge; determining for each iterative loop whether there are dependence cycles within its respective level dependence graph; and if an iterative loop from the plurality of iterative loops has no vectorization preventing dependence edges and no dependence cycles within its respective level dependence graph, indicating that the iterative loop is vectorizable; and if more than one iterative loop is vectorizable, applying a selection criteria to select an optimal iterative loop from the plurality of iterative loops.