FORMAL EQUIVALENCE CHECKING FOR LOOP OPTIMIZATION IN C PROGRAMS WITHOUT UNROLLING

摘要

In this paper, we propose an equivalence checking method for loop optimizations. Those optimizations are effective to improve the performance of both hardware and software. In our proposed method, a symbolic simulation based method is used to check the equivalence. Before applying symbolic simulation, loops are usually unrolled by certain number of times. This causes two problems. One is that the equivalence of the whole loop executions is not guaranteed if the number of unrolling is not large enough. The other is that the verification time can be very long if the loops are unrolled many times. To solve the problems, we propose the method to verify the equivalence of programs including loops and array accesses without unrolling. In the method, we extract the relations of array indexes and iterators of loops, and find the symbolic values of the iterators, for which the loops need to be executed to compute the output arrays of arbitrary indexes. Then, symbolic simulation is applied only to the specified iterations by setting the iterators to particular symbolic values. Thus, in most cases, symbolic simulation can complete the task within very small number of iterations. Finally, we show the experimental results on several loop optimizations.