[AArch64][SVE][LV][InstCombine][Unroll] Long compile times caused by interleaved accesses

[mcinally]

Long compile times are being seen on Neoverse-V2 from excessive interleaving. There are a number of components causing the code explosion, so I'll present the problem as a whole, rather than focus on one particular component.

The problem is that we have a reduction over a 284x10x16x5 array. After initial unrolling, then vectorization/interleaving, we end up with a number of copies of our loops. Then later, unrolling kicks in again and fully unrolls the inner loops. This leaves us with 5438 interleaved accesses in our outer loop. The large number of interleaved loads/stores ends up clogging up InstCombine to a small extent. And then later, the interleaved loads end up fully clogging InterleavedLoadCombine, since that pass does some analysis that compares every interleaved load in the function against every other interleaved load.

https://godbolt.org/z/7TaYY9j9h

$ /usr/bin/time -p opt '-passes=default<O3>' -mcpu=neoverse-v2 test.ll -S -o test.llvm
real 51.92
user 51.91
sys 0.00
$ /usr/bin/time -p llc test.llvm -mcpu=neoverse-v2 -O3 -o test.o
real 209.44
user 209.35
sys 0.02
$ cat test.ll
target triple = "aarch64-linux"

define void @interleave() {
L.entry:
	%foo = alloca [227200 x i32]
	%bar = alloca i32
	%.ndk0006_506 = alloca i64
	%.x0513_598 = alloca i64
	%.G0001_609 = alloca ptr
	%.ndk0010_516 = alloca i64
	%.ndk0014_526 = alloca i64
	%.ndk0018_536 = alloca i64
	%.ndk0022_546 = alloca i64
	%xxx = alloca i32
	%yyy = alloca i32
	br label %L.LB1_347
L.LB1_347:
	call void  @init(ptr %foo); 
	store i32 0, ptr %bar; 
	store i64 0, ptr %.ndk0006_506; 
	br label %L.LB1_510
L.LB1_510:
	store i64 142, ptr %.x0513_598; 
	%0 = getelementptr i8, ptr %foo, i64 -194260; 
	%1 = load i64, ptr %.ndk0006_506; 
	%2 = add i64  %1, 1; 
	%3 = mul i64  %2, 2840; 
	%4 = add i64  %3, 45726; 
	%5 = mul i64  %4, 4; 
	%6 = getelementptr i8, ptr  %0, i64  %5; 
	store ptr  %6, ptr %.G0001_609; 
	br label %L.LB1_515
L.LB1_515:
	%7 = load i32, ptr %bar; 
	%8 = load ptr, ptr %.G0001_609; 
	%9 = getelementptr i8, ptr  %8, i64 -4; 
	%10 = load i32, ptr  %9; 
	%11 = add i32  %7,  %10; 
	%12 = load ptr, ptr %.G0001_609; 
	%13 = load i32, ptr  %12; 
	%14 = add i32  %11,  %13; 
	store i32  %14, ptr %bar; 
	%15 = getelementptr i8, ptr  %8, i64 8; 
	store ptr  %15, ptr %.G0001_609; 
	%16 = load i64, ptr %.x0513_598; 
	%17 = sub i64  %16, 1; 
	store i64  %17, ptr %.x0513_598; 
	%18 = icmp sgt i64  %17, 0; 
	br i1  %18, label %L.LB1_515, label %L.LB1_661; 
L.LB1_661:
	%19 = load i64, ptr %.ndk0006_506; 
	%20 = add i64  %19, 1; 
	store i64  %20, ptr %.ndk0006_506; 
	%21 = icmp slt i64  %20, 16; 
	br i1  %21, label %L.LB1_510, label %L.LB1_662; 
L.LB1_662:
	store i64 0, ptr %.ndk0010_516; 
	br label %L.LB1_520
L.LB1_520:
	store i64 142, ptr %.x0513_598; 
	%22 = getelementptr i8, ptr %foo, i64 -194260; 
	%23 = load i64, ptr %.ndk0010_516; 
	%24 = add i64  %23, 1; 
	%25 = mul i64  %24, 2840; 
	%26 = add i64  %25, 91166; 
	%27 = mul i64  %26, 4; 
	%28 = getelementptr i8, ptr  %22, i64  %27; 
	store ptr  %28, ptr %.G0001_609; 
	br label %L.LB1_525
L.LB1_525:
	%29 = load i32, ptr %bar; 
	%30 = load ptr, ptr %.G0001_609; 
	%31 = getelementptr i8, ptr  %30, i64 -4; 
	%32 = load i32, ptr  %31; 
	%33 = add i32  %29,  %32; 
	%34 = load ptr, ptr %.G0001_609; 
	%35 = load i32, ptr  %34; 
	%36 = add i32  %33,  %35; 
	store i32  %36, ptr %bar; 
	%37 = getelementptr i8, ptr  %30, i64 8; 
	store ptr  %37, ptr %.G0001_609; 
	%38 = load i64, ptr %.x0513_598; 
	%39 = sub i64  %38, 1; 
	store i64  %39, ptr %.x0513_598; 
	%40 = icmp sgt i64  %39, 0; 
	br i1  %40, label %L.LB1_525, label %L.LB1_663; 
L.LB1_663:
	%41 = load i64, ptr %.ndk0010_516; 
	%42 = add i64  %41, 1; 
	store i64  %42, ptr %.ndk0010_516; 
	%43 = icmp slt i64  %42, 16; 
	br i1  %43, label %L.LB1_520, label %L.LB1_664; 
L.LB1_664:
	store i64 0, ptr %.ndk0014_526; 
	br label %L.LB1_530
L.LB1_530:
	store i64 142, ptr %.x0513_598; 
	%44 = getelementptr i8, ptr %foo, i64 -194260; 
	%45 = load i64, ptr %.ndk0014_526; 
	%46 = add i64  %45, 1; 
	%47 = mul i64  %46, 2840; 
	%48 = add i64  %47, 136606; 
	%49 = mul i64  %48, 4; 
	%50 = getelementptr i8, ptr  %44, i64  %49; 
	store ptr  %50, ptr %.G0001_609; 
	br label %L.LB1_535
L.LB1_535:
	%51 = load i32, ptr %bar; 
	%52 = load ptr, ptr %.G0001_609; 
	%53 = getelementptr i8, ptr  %52, i64 -4; 
	%54 = load i32, ptr  %53; 
	%55 = add i32  %51,  %54; 
	%56 = load ptr, ptr %.G0001_609; 
	%57 = load i32, ptr  %56; 
	%58 = add i32  %55,  %57; 
	store i32  %58, ptr %bar; 
	%59 = getelementptr i8, ptr  %52, i64 8; 
	store ptr  %59, ptr %.G0001_609; 
	%60 = load i64, ptr %.x0513_598; 
	%61 = sub i64  %60, 1; 
	store i64  %61, ptr %.x0513_598; 
	%62 = icmp sgt i64  %61, 0; 
	br i1  %62, label %L.LB1_535, label %L.LB1_665; 
L.LB1_665:
	%63 = load i64, ptr %.ndk0014_526; 
	%64 = add i64  %63, 1; 
	store i64  %64, ptr %.ndk0014_526; 
	%65 = icmp slt i64  %64, 16; 
	br i1  %65, label %L.LB1_530, label %L.LB1_666; 
L.LB1_666:
	store i64 0, ptr %.ndk0018_536; 
	br label %L.LB1_540
L.LB1_540:
	store i64 142, ptr %.x0513_598; 
	%66 = getelementptr i8, ptr %foo, i64 -194260; 
	%67 = load i64, ptr %.ndk0018_536; 
	%68 = add i64  %67, 1; 
	%69 = mul i64  %68, 2840; 
	%70 = add i64  %69, 182046; 
	%71 = mul i64  %70, 4; 
	%72 = getelementptr i8, ptr  %66, i64  %71; 
	store ptr  %72, ptr %.G0001_609; 
	br label %L.LB1_545
L.LB1_545:
	%73 = load i32, ptr %bar; 
	%74 = load ptr, ptr %.G0001_609; 
	%75 = getelementptr i8, ptr  %74, i64 -4; 
	%76 = load i32, ptr  %75; 
	%77 = add i32  %73,  %76; 
	%78 = load ptr, ptr %.G0001_609; 
	%79 = load i32, ptr  %78; 
	%80 = add i32  %77,  %79; 
	store i32  %80, ptr %bar; 
	%81 = getelementptr i8, ptr  %74, i64 8; 
	store ptr  %81, ptr %.G0001_609; 
	%82 = load i64, ptr %.x0513_598; 
	%83 = sub i64  %82, 1; 
	store i64  %83, ptr %.x0513_598; 
	%84 = icmp sgt i64  %83, 0; 
	br i1  %84, label %L.LB1_545, label %L.LB1_667; 
L.LB1_667:
	%85 = load i64, ptr %.ndk0018_536; 
	%86 = add i64  %85, 1; 
	store i64  %86, ptr %.ndk0018_536; 
	%87 = icmp slt i64  %86, 16; 
	br i1  %87, label %L.LB1_540, label %L.LB1_668; 
L.LB1_668:
	store i64 0, ptr %.ndk0022_546; 
	br label %L.LB1_550
L.LB1_550:
	store i64 142, ptr %.x0513_598; 
	%88 = getelementptr i8, ptr %foo, i64 -194260; 
	%89 = load i64, ptr %.ndk0022_546; 
	%90 = add i64  %89, 1; 
	%91 = mul i64  %90, 2840; 
	%92 = add i64  %91, 227486; 
	%93 = mul i64  %92, 4; 
	%94 = getelementptr i8, ptr  %88, i64  %93; 
	store ptr  %94, ptr %.G0001_609; 
	br label %L.LB1_555
L.LB1_555:
	%95 = load i32, ptr %bar; 
	%96 = load ptr, ptr %.G0001_609; 
	%97 = getelementptr i8, ptr  %96, i64 -4; 
	%98 = load i32, ptr  %97; 
	%99 = add i32  %95,  %98; 
	%100 = load ptr, ptr %.G0001_609; 
	%101 = load i32, ptr  %100; 
	%102 = add i32  %99,  %101; 
	store i32  %102, ptr %bar; 
	%103 = getelementptr i8, ptr  %96, i64 8; 
	store ptr  %103, ptr %.G0001_609; 
	%104 = load i64, ptr %.x0513_598; 
	%105 = sub i64  %104, 1; 
	store i64  %105, ptr %.x0513_598; 
	%106 = icmp sgt i64  %105, 0; 
	br i1  %106, label %L.LB1_555, label %L.LB1_669; 
L.LB1_669:
	%107 = load i64, ptr %.ndk0022_546; 
	%108 = add i64  %107, 1; 
	store i64  %108, ptr %.ndk0022_546; 
	%109 = icmp slt i64  %108, 16; 
	br i1  %109, label %L.LB1_550, label %L.LB1_670; 
L.LB1_670:
	%110 = load i32, ptr %bar; 
	store i32  %110, ptr %xxx; 
	%111 = load i32, ptr %xxx; 
	%112 = call i32  @use(i32  %111); 
	ret void; 
}

declare i32 @use();
declare void @init();

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Cameron McInally (mcinally)

Long compile times are being seen on Neoverse-V2 from excessive interleaving. There are a number of components causing the code explosion, so I'll present the problem as a whole, rather than focus on one particular component.

The problem is that we have a reduction over a 284x10x16x5 array. After initial unrolling, then vectorization/interleaving, we end up with a number of copies of our loops. Then later, unrolling kicks in again and fully unrolls the inner loops. This leaves us with 5438 interleaved accesses in our outer loop. The large number of interleaved loads/stores ends up clogging up InstCombine to a small extent. And then later, the interleaved loads end up fully clogging InterleavedLoadCombine, since that pass does some analysis that compares every interleaved load in the function against every other interleaved load.

$ /usr/bin/time -p opt '-passes=default<O3>' -mcpu=neoverse-v2 test.ll -S -o test.llvm
real 51.92
user 51.91
sys 0.00
$ /usr/bin/time -p llc test.llvm -mcpu=neoverse-v2 -O3 -o test.o
real 209.44
user 209.35
sys 0.02
$ cat test.ll
target triple = "aarch64-linux"

define void @<!-- -->interleave() {
L.entry:
	%foo = alloca [227200 x i32]
	%bar = alloca i32
	%.ndk0006_506 = alloca i64
	%.x0513_598 = alloca i64
	%.G0001_609 = alloca ptr
	%.ndk0010_516 = alloca i64
	%.ndk0014_526 = alloca i64
	%.ndk0018_536 = alloca i64
	%.ndk0022_546 = alloca i64
	%xxx = alloca i32
	%yyy = alloca i32
	br label %L.LB1_347
L.LB1_347:
	call void  @<!-- -->init(ptr %foo); 
	store i32 0, ptr %bar; 
	store i64 0, ptr %.ndk0006_506; 
	br label %L.LB1_510
L.LB1_510:
	store i64 142, ptr %.x0513_598; 
	%0 = getelementptr i8, ptr %foo, i64 -194260; 
	%1 = load i64, ptr %.ndk0006_506; 
	%2 = add i64  %1, 1; 
	%3 = mul i64  %2, 2840; 
	%4 = add i64  %3, 45726; 
	%5 = mul i64  %4, 4; 
	%6 = getelementptr i8, ptr  %0, i64  %5; 
	store ptr  %6, ptr %.G0001_609; 
	br label %L.LB1_515
L.LB1_515:
	%7 = load i32, ptr %bar; 
	%8 = load ptr, ptr %.G0001_609; 
	%9 = getelementptr i8, ptr  %8, i64 -4; 
	%10 = load i32, ptr  %9; 
	%11 = add i32  %7,  %10; 
	%12 = load ptr, ptr %.G0001_609; 
	%13 = load i32, ptr  %12; 
	%14 = add i32  %11,  %13; 
	store i32  %14, ptr %bar; 
	%15 = getelementptr i8, ptr  %8, i64 8; 
	store ptr  %15, ptr %.G0001_609; 
	%16 = load i64, ptr %.x0513_598; 
	%17 = sub i64  %16, 1; 
	store i64  %17, ptr %.x0513_598; 
	%18 = icmp sgt i64  %17, 0; 
	br i1  %18, label %L.LB1_515, label %L.LB1_661; 
L.LB1_661:
	%19 = load i64, ptr %.ndk0006_506; 
	%20 = add i64  %19, 1; 
	store i64  %20, ptr %.ndk0006_506; 
	%21 = icmp slt i64  %20, 16; 
	br i1  %21, label %L.LB1_510, label %L.LB1_662; 
L.LB1_662:
	store i64 0, ptr %.ndk0010_516; 
	br label %L.LB1_520
L.LB1_520:
	store i64 142, ptr %.x0513_598; 
	%22 = getelementptr i8, ptr %foo, i64 -194260; 
	%23 = load i64, ptr %.ndk0010_516; 
	%24 = add i64  %23, 1; 
	%25 = mul i64  %24, 2840; 
	%26 = add i64  %25, 91166; 
	%27 = mul i64  %26, 4; 
	%28 = getelementptr i8, ptr  %22, i64  %27; 
	store ptr  %28, ptr %.G0001_609; 
	br label %L.LB1_525
L.LB1_525:
	%29 = load i32, ptr %bar; 
	%30 = load ptr, ptr %.G0001_609; 
	%31 = getelementptr i8, ptr  %30, i64 -4; 
	%32 = load i32, ptr  %31; 
	%33 = add i32  %29,  %32; 
	%34 = load ptr, ptr %.G0001_609; 
	%35 = load i32, ptr  %34; 
	%36 = add i32  %33,  %35; 
	store i32  %36, ptr %bar; 
	%37 = getelementptr i8, ptr  %30, i64 8; 
	store ptr  %37, ptr %.G0001_609; 
	%38 = load i64, ptr %.x0513_598; 
	%39 = sub i64  %38, 1; 
	store i64  %39, ptr %.x0513_598; 
	%40 = icmp sgt i64  %39, 0; 
	br i1  %40, label %L.LB1_525, label %L.LB1_663; 
L.LB1_663:
	%41 = load i64, ptr %.ndk0010_516; 
	%42 = add i64  %41, 1; 
	store i64  %42, ptr %.ndk0010_516; 
	%43 = icmp slt i64  %42, 16; 
	br i1  %43, label %L.LB1_520, label %L.LB1_664; 
L.LB1_664:
	store i64 0, ptr %.ndk0014_526; 
	br label %L.LB1_530
L.LB1_530:
	store i64 142, ptr %.x0513_598; 
	%44 = getelementptr i8, ptr %foo, i64 -194260; 
	%45 = load i64, ptr %.ndk0014_526; 
	%46 = add i64  %45, 1; 
	%47 = mul i64  %46, 2840; 
	%48 = add i64  %47, 136606; 
	%49 = mul i64  %48, 4; 
	%50 = getelementptr i8, ptr  %44, i64  %49; 
	store ptr  %50, ptr %.G0001_609; 
	br label %L.LB1_535
L.LB1_535:
	%51 = load i32, ptr %bar; 
	%52 = load ptr, ptr %.G0001_609; 
	%53 = getelementptr i8, ptr  %52, i64 -4; 
	%54 = load i32, ptr  %53; 
	%55 = add i32  %51,  %54; 
	%56 = load ptr, ptr %.G0001_609; 
	%57 = load i32, ptr  %56; 
	%58 = add i32  %55,  %57; 
	store i32  %58, ptr %bar; 
	%59 = getelementptr i8, ptr  %52, i64 8; 
	store ptr  %59, ptr %.G0001_609; 
	%60 = load i64, ptr %.x0513_598; 
	%61 = sub i64  %60, 1; 
	store i64  %61, ptr %.x0513_598; 
	%62 = icmp sgt i64  %61, 0; 
	br i1  %62, label %L.LB1_535, label %L.LB1_665; 
L.LB1_665:
	%63 = load i64, ptr %.ndk0014_526; 
	%64 = add i64  %63, 1; 
	store i64  %64, ptr %.ndk0014_526; 
	%65 = icmp slt i64  %64, 16; 
	br i1  %65, label %L.LB1_530, label %L.LB1_666; 
L.LB1_666:
	store i64 0, ptr %.ndk0018_536; 
	br label %L.LB1_540
L.LB1_540:
	store i64 142, ptr %.x0513_598; 
	%66 = getelementptr i8, ptr %foo, i64 -194260; 
	%67 = load i64, ptr %.ndk0018_536; 
	%68 = add i64  %67, 1; 
	%69 = mul i64  %68, 2840; 
	%70 = add i64  %69, 182046; 
	%71 = mul i64  %70, 4; 
	%72 = getelementptr i8, ptr  %66, i64  %71; 
	store ptr  %72, ptr %.G0001_609; 
	br label %L.LB1_545
L.LB1_545:
	%73 = load i32, ptr %bar; 
	%74 = load ptr, ptr %.G0001_609; 
	%75 = getelementptr i8, ptr  %74, i64 -4; 
	%76 = load i32, ptr  %75; 
	%77 = add i32  %73,  %76; 
	%78 = load ptr, ptr %.G0001_609; 
	%79 = load i32, ptr  %78; 
	%80 = add i32  %77,  %79; 
	store i32  %80, ptr %bar; 
	%81 = getelementptr i8, ptr  %74, i64 8; 
	store ptr  %81, ptr %.G0001_609; 
	%82 = load i64, ptr %.x0513_598; 
	%83 = sub i64  %82, 1; 
	store i64  %83, ptr %.x0513_598; 
	%84 = icmp sgt i64  %83, 0; 
	br i1  %84, label %L.LB1_545, label %L.LB1_667; 
L.LB1_667:
	%85 = load i64, ptr %.ndk0018_536; 
	%86 = add i64  %85, 1; 
	store i64  %86, ptr %.ndk0018_536; 
	%87 = icmp slt i64  %86, 16; 
	br i1  %87, label %L.LB1_540, label %L.LB1_668; 
L.LB1_668:
	store i64 0, ptr %.ndk0022_546; 
	br label %L.LB1_550
L.LB1_550:
	store i64 142, ptr %.x0513_598; 
	%88 = getelementptr i8, ptr %foo, i64 -194260; 
	%89 = load i64, ptr %.ndk0022_546; 
	%90 = add i64  %89, 1; 
	%91 = mul i64  %90, 2840; 
	%92 = add i64  %91, 227486; 
	%93 = mul i64  %92, 4; 
	%94 = getelementptr i8, ptr  %88, i64  %93; 
	store ptr  %94, ptr %.G0001_609; 
	br label %L.LB1_555
L.LB1_555:
	%95 = load i32, ptr %bar; 
	%96 = load ptr, ptr %.G0001_609; 
	%97 = getelementptr i8, ptr  %96, i64 -4; 
	%98 = load i32, ptr  %97; 
	%99 = add i32  %95,  %98; 
	%100 = load ptr, ptr %.G0001_609; 
	%101 = load i32, ptr  %100; 
	%102 = add i32  %99,  %101; 
	store i32  %102, ptr %bar; 
	%103 = getelementptr i8, ptr  %96, i64 8; 
	store ptr  %103, ptr %.G0001_609; 
	%104 = load i64, ptr %.x0513_598; 
	%105 = sub i64  %104, 1; 
	store i64  %105, ptr %.x0513_598; 
	%106 = icmp sgt i64  %105, 0; 
	br i1  %106, label %L.LB1_555, label %L.LB1_669; 
L.LB1_669:
	%107 = load i64, ptr %.ndk0022_546; 
	%108 = add i64  %107, 1; 
	store i64  %108, ptr %.ndk0022_546; 
	%109 = icmp slt i64  %108, 16; 
	br i1  %109, label %L.LB1_550, label %L.LB1_670; 
L.LB1_670:
	%110 = load i32, ptr %bar; 
	store i32  %110, ptr %xxx; 
	%111 = load i32, ptr %xxx; 
	%112 = call i32  @<!-- -->use(i32  %111); 
	ret void; 
}

declare i32 @<!-- -->use();
declare void @<!-- -->init();

[MacDue]

Out of curiosity, are these long compile times coming from a real workload, or constructed examples? Avoiding n² logic would be nice either way.

[mcinally]

Real workload, but I'll be vague out of an abundance of caution. It's one of your favorite weather forecasting codes.

[mcinally]

@kiranchandramohan for visibility.

[davemgreen]

If it is unrolling then interleaving then we should ideally be able to emit non-interleaved instructions in the vectorizer.