[llvm-bugs] [Bug 52123] New: Unlimited loop unrolling leads to non-linear compilation times

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=52123

            Bug ID: 52123
           Summary: Unlimited loop unrolling leads to non-linear
                    compilation times
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: simonas+llvm.org at kazlauskas.me
                CC: llvm-bugs at lists.llvm.org

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
https://github.com/rust-lang/rust/issues/74384

-- 
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/20211009/3736b24d/attachment.html>