<html>
<head>
<base href="http://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - ScopStmt::realignParams() takes a long time"
href="http://bugs.llvm.org/show_bug.cgi?id=32152">32152</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>ScopStmt::realignParams() takes a long time
</td>
</tr>
<tr>
<th>Product</th>
<td>Polly
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Other
</td>
</tr>
<tr>
<th>Assignee</th>
<td>polly-dev@googlegroups.com
</td>
</tr>
<tr>
<th>Reporter</th>
<td>llvm@meinersbur.de
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=18057" name="attach_18057" title="patricia_0.ll">attachment 18057</a> <a href="attachment.cgi?id=18057&action=edit" title="patricia_0.ll">[details]</a></span>
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>