1 #!/usr/bin/env python3
3 # This is an implementation of the algorithm described in
4 #
5 # [ACI10] C. Ancourt, F. Coelho and F. Irigoin, A modular static analysis
6 # approach to affine loop invariants detection (2010), pp. 3 - 16, NSAD 2010.
7 #
8 # to compute the transitive closure of an affine transformer. A refined version
9 # of this algorithm is implemented in PIPS.
11 from linpy import Dummy, Eq, Ge, Polyhedron, symbols
14 class Transformer:
16 def __new__(cls, polyhedron, range_symbols, domain_symbols):
17 self = object().__new__(cls)
18 self.polyhedron = polyhedron
19 self.range_symbols = range_symbols
20 self.domain_symbols = domain_symbols
21 return self
23 @property
24 def symbols(self):
25 return self.range_symbols + self.domain_symbols
27 def star(self):
28 delta_symbols = [symbol.asdummy() for symbol in self.range_symbols]
29 k = Dummy('k')
30 polyhedron = self.polyhedron
31 for x, xprime, dx in zip(
32 self.range_symbols, self.domain_symbols, delta_symbols):
33 polyhedron &= Eq(dx, xprime - x)
34 polyhedron = polyhedron.project(self.symbols)
35 equalities, inequalities = [], []
36 for equality in polyhedron.equalities:
37 equality += (k-1) * equality.constant
38 equalities.append(equality)
39 for inequality in polyhedron.inequalities:
40 inequality += (k-1) * inequality.constant
41 inequalities.append(inequality)
42 polyhedron = Polyhedron(equalities, inequalities) & Ge(k, 0)
43 polyhedron = polyhedron.project([k])
44 for x, xprime, dx in zip(
45 self.range_symbols, self.domain_symbols, delta_symbols):
46 polyhedron &= Eq(dx, xprime - x)
47 polyhedron = polyhedron.project(delta_symbols)
48 return Transformer(polyhedron, self.range_symbols, self.domain_symbols)
51 if __name__ == '__main__':
52 i0, i, j0, j = symbols('i0 i j0 j')
53 transformer = Transformer(Eq(i, i0 + 2) & Eq(j, j0 + 1),
54 [i0, j0], [i, j])
55 print('T =', transformer.polyhedron)
56 print('T* =', transformer.star().polyhedron)