X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/90d7f21ee1486524f499f66ef546a24331b2009c..37902ff90b8bfe94b10bd1a99ddd6e040cede027:/examples/nsad2010.py diff --git a/examples/nsad2010.py b/examples/nsad2010.py index 8194618..4b73eef 100755 --- a/examples/nsad2010.py +++ b/examples/nsad2010.py @@ -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)