<html>
<head>
<base href="https://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 - Execution time of Bitcode Writer grows exponentially with number of loop rounds"
href="https://bugs.llvm.org/show_bug.cgi?id=45545">45545</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Execution time of Bitcode Writer grows exponentially with number of loop rounds
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</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>Bitcode Writer
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>mikael.holmen@ericsson.com
</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=23359" name="attach_23359" title="bbi-41722.ll reproducer">attachment 23359</a> <a href="attachment.cgi?id=23359&action=edit" title="bbi-41722.ll reproducer">[details]</a></span>
bbi-41722.ll reproducer
Reproducer:
opt -o /dev/null bbi-41722.ll -indvars
In the input the number of loop iterations is determined by the constant in the
following phi instruction:
%i.0 = phi i16 [ 12, %entry ], [ %dec, %for.body ]
With -debug-pass=Executions we can see the execution time for the 'Bitcode
Writer' pass for different iteration counts.
N : time : bc output size
10: 0.3s : 1820
11: 1.6s : 1876
12: 8.1s : 1932
13: 35s : 1992
14: 3m : 2052
so the time increases exponentially but the size of the output doesn't.
The increased time seems to be spent in ValueEnumerator::EnumerateOperandType
called from the ValueEnumerator constructor:
for (const BasicBlock &BB : F)
for (const Instruction &I : BB) {
for (const Use &Op : I.operands()) {
auto *MD = dyn_cast<MetadataAsValue>(&Op);
if (!MD) {
EnumerateOperandType(Op);
continue;
}
For N == 2 we get this load instruction after -indvars, as printed with
-print-after-all:
store i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1
icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to
i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to
i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16
zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16
0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast
(i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16 xor (i16 lshr
(i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to
i16**), i16** @f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0,
i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to
i16**), i16** @f.c) to i16), i16 0) to i16))), i16* @f.a, align 1
For N == 3:
store i16 sub (i16 zext (i1 icmp sgt (i16 sub (i16 zext (i1 icmp sgt (i16
zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**),
i16** @f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16*
@f.a to i16**), i16** @f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and
(i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to
i16**), i16** @f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt
(i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16),
i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16
15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16))), i16
zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16)) to
i16), i16 select (i1 icmp slt (i16 and (i16 sub (i16 zext (i1 icmp sgt (i16
zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**),
i16** @f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16*
@f.a to i16**), i16** @f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and
(i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to
i16**), i16** @f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt
(i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16),
i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16
15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16))), i16
add (i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp
eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16),
i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16))
to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1
icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to
i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16*
@f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16
zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**),
i16** @f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16
zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**),
i16** @f.c) to i16), i16 0) to i16))), i16 xor (i16 lshr (i16 sub (i16 zext (i1
icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a
to i16**), i16** @f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16**
bitcast (i16* @f.a to i16**), i16** @f.c) to i16)) to i16), i16 select (i1 icmp
slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16*
@f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp
slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to
i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1
icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to
i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1
icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to
i16))), i16 15), i16 -1))), i16 0), i16 0, i16 sub (i16 zext (i1 icmp sgt (i16
zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**),
i16** @f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16*
@f.a to i16**), i16** @f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and
(i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to
i16**), i16** @f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt
(i16 zext (i1 icmp eq (i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16),
i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16), i16
15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq
(i16** bitcast (i16* @f.a to i16**), i16** @f.c) to i16), i16 0) to i16))))),
i16* @f.a, align 1
etc.
I think that ValueEnumerator::EnumerateOperandType is called recursively on
each operand in the constant expression.</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>