index 8194618..4b73eef 100755 (executable)
@@ -1,6 +1,14 @@
#!/usr/bin/env python3

-from pypol import *
+# This is an implementation of the algorithm described in
+#
+# [ACI10] C. Ancourt, F. Coelho and F. Irigoin, A modular static analysis
+# approach to affine loop invariants detection (2010), pp. 3 - 16, NSAD 2010.
+#
+# to compute the transitive closure of an affine transformer. A refined version
+# of this algorithm is implemented in PIPS.
+
+from linpy import *

class Transformer:
@@ -22,7 +30,7 @@ class Transformer:
polyhedron = self.polyhedron
for x, xprime, dx in zip(self.range_symbols, self.domain_symbols, delta_symbols):
polyhedron &= Eq(dx, xprime - x)
-        polyhedron = polyhedron.project_out(self.symbols)
+        polyhedron = polyhedron.project(self.symbols)
equalities, inequalities = [], []
for equality in polyhedron.equalities:
equality += (k-1) * equality.constant
@@ -31,16 +39,16 @@ class Transformer:
inequality += (k-1) * inequality.constant
inequalities.append(inequality)
polyhedron = Polyhedron(equalities, inequalities) & Ge(k, 0)
-        polyhedron = polyhedron.project_out([k])
+        polyhedron = polyhedron.project([k])
for x, xprime, dx in zip(self.range_symbols, self.domain_symbols, delta_symbols):
polyhedron &= Eq(dx, xprime - x)
-        polyhedron = polyhedron.project_out(delta_symbols)
+        polyhedron = polyhedron.project(delta_symbols)
return Transformer(polyhedron, self.range_symbols, self.domain_symbols)

if __name__ == '__main__':
-    i, iprime, j, jprime = symbols("i i' j j'")
-    transformer = Transformer(Eq(iprime, i + 2) & Eq(jprime, j + 1),
-        [i, j], [iprime, jprime])
+    i0, i, j0, j = symbols('i0 i j0 j')
+    transformer = Transformer(Eq(i, i0 + 2) & Eq(j, j0 + 1),
+        [i0, j0], [i, j])
print('T  =', transformer.polyhedron)
print('T* =', transformer.star().polyhedron)