SIMD vectorization of nested loop based on strip mining

The difference between vector machine and SIMD extension is analyzed at the very start. The multilevel loop vector code generation algorithm termed Codegen put forward by Kennedy and other fellows can´t be directly applied to SIMD extension as it is oriented to vector machine. The vectorization algorithm in state-of-the-art compilers can only process one level of nested loop. In order to vectorize the entire nested loop, a vectorization algorithm based on strip mining called simdcodegen is proposed. Firstly, the formation reason of dependence circles is analyzed and the role of strip mining played in elimination of dependence circles is discussed. Then on the basis of codegen, strip mining is applied on each level of the loop recursively to explore the SIMD parallelism in the nested loop. Although strip mining is always legitimate, the executing cost increases after strip mining. To assure that strip mining is beneficial, that is to say, strip mining can break some dependence circles, cycle broken test is applied before implementation of strip mining. Effectiveness of this method is verified by the experimental results.