Static analysis of arithmetical congruences

Abstract

In this paper, a new kind of static (or semantic) analysis is defined: congruence analysis, which is conceived to discover the properties of the following type: “the integer valued variable X is congruent to c modulo m”, where c and m are automatically determined integers. This analysis is then related to an algebraic framework and wholly characterized. Moreover, we show an example how it can be useful for automatic vectorization. Finally, we present some extensions of it, namely its combination with the analysis of bounds, and also some analyses defined when the modulus of congruences is given a priori.