<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 - Unlimited loop unrolling leads to non-linear compilation times"
href="https://bugs.llvm.org/show_bug.cgi?id=52123">52123</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Unlimited loop unrolling leads to non-linear compilation times
</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>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Loop Optimizer
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>simonas+llvm.org@kazlauskas.me
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Consider code such as this:
```
target datalayout =
"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
define void @foo([15 x [15 x [15 x { i8, i8 }]]]* noalias nocapture sret([15 x
[15 x [15 x { i8, i8 }]]]) dereferenceable(6750) %0) {
%2 = alloca [15 x { i8, i8 }], align 1
%3 = alloca [15 x [15 x { i8, i8 }]], align 1
%4 = getelementptr inbounds [15 x [15 x { i8, i8 }]], [15 x [15 x { i8, i8
}]]* %3, i64 0, i64 0, i64 0, i32 0
%5 = getelementptr inbounds [15 x { i8, i8 }], [15 x { i8, i8 }]* %2, i64 0,
i64 0, i32 0
%6 = getelementptr inbounds [15 x { i8, i8 }], [15 x { i8, i8 }]* %2, i64 0,
i64 0
%7 = getelementptr inbounds [15 x { i8, i8 }], [15 x { i8, i8 }]* %2, i64 0,
i64 15
br label %8
8: ; preds = %1, %8
%9 = phi { i8, i8 }* [ %6, %1 ], [ %11, %8 ]
%10 = getelementptr inbounds { i8, i8 }, { i8, i8 }* %9, i64 0, i32 0
store i8 0, i8* %10, align 1
%11 = getelementptr inbounds { i8, i8 }, { i8, i8 }* %9, i64 1
%12 = icmp eq { i8, i8 }* %11, %7
br i1 %12, label %13, label %8
13: ; preds = %8
%14 = getelementptr inbounds [15 x [15 x { i8, i8 }]], [15 x [15 x { i8, i8
}]]* %3, i64 0, i64 0
%15 = getelementptr inbounds [15 x [15 x { i8, i8 }]], [15 x [15 x { i8, i8
}]]* %3, i64 0, i64 15
br label %16
16: ; preds = %13, %16
%17 = phi [15 x { i8, i8 }]* [ %14, %13 ], [ %19, %16 ]
%18 = getelementptr [15 x { i8, i8 }], [15 x { i8, i8 }]* %17, i64 0, i64 0,
i32 0
call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1
dereferenceable(30) %18, i8* noundef nonnull align 1 dereferenceable(30) %5,
i64 30, i1 false)
%19 = getelementptr inbounds [15 x { i8, i8 }], [15 x { i8, i8 }]* %17, i64 1
%20 = icmp eq [15 x { i8, i8 }]* %19, %15
br i1 %20, label %21, label %16
21: ; preds = %16
%22 = getelementptr inbounds [15 x [15 x [15 x { i8, i8 }]]], [15 x [15 x [15
x { i8, i8 }]]]* %0, i64 0, i64 0
%23 = getelementptr inbounds [15 x [15 x [15 x { i8, i8 }]]], [15 x [15 x [15
x { i8, i8 }]]]* %0, i64 0, i64 15
br label %24
24: ; preds = %21, %24
%25 = phi [15 x [15 x { i8, i8 }]]* [ %22, %21 ], [ %27, %24 ]
%26 = getelementptr [15 x [15 x { i8, i8 }]], [15 x [15 x { i8, i8 }]]* %25,
i64 0, i64 0, i64 0, i32 0
call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1
dereferenceable(450) %26, i8* noundef nonnull align 1 dereferenceable(450) %4,
i64 450, i1 false)
%27 = getelementptr inbounds [15 x [15 x { i8, i8 }]], [15 x [15 x { i8, i8
}]]* %25, i64 1
%28 = icmp eq [15 x [15 x { i8, i8 }]]* %27, %23
br i1 %28, label %29, label %24
29: ; preds = %24
ret void
}
; Function Attrs: argmemonly nofree nounwind willreturn
declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8*
noalias nocapture readonly, i64, i1 immarg) #1
attributes #1 = { argmemonly nofree nounwind willreturn }
```
This is a N=15 loop nested 3 times. LLVM will unroll this loop into N^3
instructions, and the overall build time will be quadratic over N as a result.
Here are `opt -O3 | llc -O3` times with a choice of N values:
N=15 t=115ms
N=20 t=240ms
N=25 t=500ms
N=30 t=1s
A similar problem can be observed in rustc at
<a href="https://github.com/rust-lang/rust/issues/74384">https://github.com/rust-lang/rust/issues/74384</a></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>