examples/nsad2010.py

   1 #!/usr/bin/env python3
   2
   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.
  10
  11 from linpy import Dummy, Eq, Ge, Polyhedron, symbols
  12
  13
  14 class Transformer:
  15
  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
  22
  23     @property
  24     def symbols(self):
  25         return self.range_symbols + self.domain_symbols
  26
  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)
  49
  50
  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)