[PPL-devel] Exponential behavior in ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
Sebastian Pop
sebpop at gmail.com
Tue Mar 9 02:06:18 CET 2010
Hi,
there seems to be an exponential behavior when calling
ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
(&ps, context);
to build the scop context for the 437.leslie3d benchmark:
(gdb) p debug_ppl_polyhedron_matrix (context)
42 23
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2147483648
1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2147483647
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 9223372036854775807
$35 = void
this is equivalent to
-2147483648 <= p0 <= 2147483647
-9223372036854775808 <= p1 <= 9223372036854775807
etc.
For now, I am thinking to limit the scops that we are handling based
on the number of parameters that we have to handle to avoid for now
this kind of problems.
Roberto, is there some other output more interesting for the PPL folks
and that I should report?
Thanks,
Sebastian
PS: here is a backtrace after I stopped the execution randomly
(gdb) bt
#0 0x00002aaaab4d7f83 in Parma_Polyhedra_Library::subset_or_equal(Parma_Polyhedra_Library::Bit_Row const&, Parma_Polyhedra_Library::Bit_Row const&) () from /usr/lib/libppl.so.7
#1 0x00002aaaab4da9c0 in Parma_Polyhedra_Library::Polyhedron::conversion(Parma_Polyhedra_Library::Linear_System&, unsigned long, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Bit_Matrix&, unsigned long) () from /usr/lib/libppl.so.7
#2 0x00002aaaab4dc16b in Parma_Polyhedra_Library::Polyhedron::minimize(bool, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Bit_Matrix&) () from /usr/lib/libppl.so.7
#3 0x00002aaaab497620 in Parma_Polyhedra_Library::Polyhedron::update_generators() const () from /usr/lib/libppl.so.7
#4 0x00002aaaab0ff407 in ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron () from /usr/lib/libppl_c.so.2
#5 0x00000000010188c6 in build_scop_context (scop=0x19f0390) at ../../gcc/graphite-sese-to-poly.c:1554
More information about the PPL-devel
mailing list