[llvm-bugs] [Bug 32152] New: ScopStmt::realignParams() takes a long time

[via llvm-bugs]

http://bugs.llvm.org/show_bug.cgi?id=32152

            Bug ID: 32152
           Summary: ScopStmt::realignParams() takes a long time
           Product: Polly
           Version: unspecified
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Other
          Assignee: polly-dev at googlegroups.com
          Reporter: llvm at meinersbur.de
                CC: llvm-bugs at lists.llvm.org

Created attachment 18057
  --> http://bugs.llvm.org/attachment.cgi?id=18057&action=edit
patricia_0.ll

ScopStmt::realignParams() takes a long time (at least 30 mins, did not wait
longer)

$ opt -polly-process-unprofitable -polly-scops patricia_0.ll

The attached example has 32 statements. For every statement the execution of 

    InvalidDomain = isl_set_gist_params(InvalidDomain, isl_set_copy(Ctx));

takes longer and longer. The cause is that the coefficients are very large. For
instance with arguments

Ctx:
[p_0] -> {  : p_0 >= -9223372036854775808 and p_0 <= 9223372036854775807 }

InvalidDomain:
[p_0] -> { [] : exists (e0 = floor((4 + p_0)/8), e1 = floor((8 + p_0)/16), e2 =
floor((16 + p_0)/32), e3 = floor((32 + p_0)/64), e4 = floor((64 + p_0)/128), e5
= floor((128 + p_0)/256), e6 = floor((256 + p_0)/512), e7 = floor((512 +
p_0)/1024), e8 = floor((1024 + p_0)/2048), e9 = floor((2048 + p_0)/4096), e10 =
floor((4096 + p_0)/8192), e11 = floor((8192 + p_0)/16384), e12 = floor((16384 +
p_0)/32768), e13 = floor((32768 + p_0)/65536), e14 = floor((65536 +
p_0)/131072), e15 = floor((131072 + p_0)/262144), e16 = floor((262144 +
p_0)/524288), e17 = floor((524288 + p_0)/1048576), e18 = floor((1048576 +
p_0)/2097152), e19 = floor((2097152 + p_0)/4194304), e20 = floor((4194304 +
p_0)/8388608), e21 = floor((8388608 + p_0)/16777216), e22 = floor((16777216 +
p_0)/33554432), e23 = floor((33554432 + p_0)/67108864), e24 = floor((67108864 +
p_0)/134217728), e25 = floor((134217728 + p_0)/268435456), e26 =
floor((268435456 + p_0)/536870912), e27 = floor((536870912 + p_0)/1073741824),
e28 = floor((1073741824 + p_0)/2147483648), e29 = floor((2 + p_0)/4): p_0 < 0
and 8e0 >= -3 + p_0 and 8e0 <= p_0 and 16e1 >= -7 + p_0 and 16e1 <= p_0 and
32e2 >= -15 + p_0 and 32e2 <= p_0 and 64e3 >= -31 + p_0 and 64e3 <= p_0 and
128e4 >= -63 + p_0 and 128e4 <= p_0 and 256e5 >= -127 + p_0 and 256e5 <= p_0
and 512e6 >= -255 + p_0 and 512e6 <= p_0 and 1024e7 >= -511 + p_0 and 1024e7 <=
p_0 and 2048e8 >= -1023 + p_0 and 2048e8 <= p_0 and 4096e9 >= -2047 + p_0 and
4096e9 <= p_0 and 8192e10 >= -4095 + p_0 and 8192e10 <= p_0 and 16384e11 >=
-8191 + p_0 and 16384e11 <= p_0 and 32768e12 >= -16383 + p_0 and 32768e12 <=
p_0 and 65536e13 >= -32767 + p_0 and 65536e13 <= p_0 and 131072e14 >= -65535 +
p_0 and 131072e14 <= p_0 and 262144e15 >= -131071 + p_0 and 262144e15 <= p_0
and 524288e16 >= -262143 + p_0 and 524288e16 <= p_0 and 1048576e17 >= -524287 +
p_0 and 1048576e17 <= p_0 and 2097152e18 >= -1048575 + p_0 and 2097152e18 <=
p_0 and 4194304e19 >= -2097151 + p_0 and 4194304e19 <= p_0 and 8388608e20 >=
-4194303 + p_0 and 8388608e20 <= p_0 and 16777216e21 >= -8388607 + p_0 and
16777216e21 <= p_0 and 33554432e22 >= -16777215 + p_0 and 33554432e22 <= p_0
and 67108864e23 >= -33554431 + p_0 and 67108864e23 <= p_0 and 134217728e24 >=
-67108863 + p_0 and 134217728e24 <= p_0 and 268435456e25 >= -134217727 + p_0
and 268435456e25 <= p_0 and 536870912e26 >= -268435455 + p_0 and 536870912e26
<= p_0 and 1073741824e27 >= -536870911 + p_0 and 1073741824e27 <= p_0 and
2147483648e28 >= -1073741823 + p_0 and 2147483648e28 <= p_0 and 4e29 >= -1 +
p_0 and 4e29 <= p_0) }

the operation already takes longer than I was willing to wait. One of the
causes is that with large coefficients, the small-int optimization in isl falls
back to imath and gets even slower. isl_set_gist_params doesn't even simplify
the InvalidDomain polyhedron.

Strangely, when I try to reproduce this in plain isl, with
isl_set_read_from_str, it takes not quite as long. Some internal isl structures
might be different.

Polly r296994.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170306/2b76e3f0/attachment.html>