Excessive compile time in SelectionDAG with large arrays

[AnFunctionArray]

If wondering this happened while testing out yarpgen with my own frontend. - other compiles work fine but this specific ones hangs seemingly forever.

llc --version

LLVM (http://llvm.org/):
  LLVM version 15.0.0git
  Optimized build.
  Default target: arm64-apple-darwin21.5.0
  Host CPU: apple-m1

  Registered Targets:
    aarch64    - AArch64 (little endian)
    aarch64_32 - AArch64 (little endian ILP32)
    aarch64_be - AArch64 (big endian)
    amdgcn     - AMD GCN GPUs
    arm        - ARM
    arm64      - ARM64 (little endian)
    arm64_32   - ARM64 (little endian ILP32)
    armeb      - ARM (big endian)
    avr        - Atmel AVR Microcontroller
    bpf        - BPF (host endian)
    bpfeb      - BPF (big endian)
    bpfel      - BPF (little endian)
    hexagon    - Hexagon
    lanai      - Lanai
    mips       - MIPS (32-bit big endian)
    mips64     - MIPS (64-bit big endian)
    mips64el   - MIPS (64-bit little endian)
    mipsel     - MIPS (32-bit little endian)
    msp430     - MSP430 [experimental]
    nvptx      - NVIDIA PTX 32-bit
    nvptx64    - NVIDIA PTX 64-bit
    ppc32      - PowerPC 32
    ppc32le    - PowerPC 32 LE
    ppc64      - PowerPC 64
    ppc64le    - PowerPC 64 LE
    r600       - AMD GPUs HD2XXX-HD6XXX
    riscv32    - 32-bit RISC-V
    riscv64    - 64-bit RISC-V
    sparc      - Sparc
    sparcel    - Sparc LE
    sparcv9    - Sparc V9
    systemz    - SystemZ
    thumb      - Thumb
    thumbeb    - Thumb (big endian)
    ve         - VE
    wasm32     - WebAssembly 32-bit
    wasm64     - WebAssembly 64-bit
    x86        - 32-bit X86: Pentium-Pro and above
    x86-64     - 64-bit X86: EM64T and AMD64
    xcore      - XCore

The following command on my Mac air:

/usr/local/bin/llc -filetype=obj -o ./func.o ./func.pp.ll

func.pp.ll (content):

(uploaded to file due to message body being too long func.pp.ll.log )

[RKSimon]

bugpoint reduced:

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "func.pp"
target triple = "x86_64-unknown-linux-gnu"

@arr_7 = external global [11 x [11 x i8]]
@arr_8 = external global [11 x [11 x i32]]
@arr_9 = external global [11 x [11 x i8]]
@var_20 = external global i64
@var_21 = external global i64
@arr_14 = external global [16 x [10 x i8]]
@var_22 = external global i64
@arr_21 = external global [16 x [10 x [24 x [10 x i32]]]]
@var_23 = external global i16
@arr_22 = external global [16 x [10 x [24 x [10 x i32]]]]
@arr_27 = external global [16 x [10 x [24 x [10 x [21 x i16]]]]]
@arr_28 = external global [16 x [10 x [24 x [10 x [21 x i8]]]]]
@arr_29 = external global [16 x [10 x [24 x [10 x [21 x i8]]]]]
@arr_30 = external global [16 x [10 x [24 x [10 x [21 x i32]]]]]
@var_24 = external global i8
@var_25 = external global i64
@arr_33 = external global [16 x [10 x [24 x [10 x [14 x i64]]]]]
@arr_34 = external global [16 x [10 x [24 x [10 x [14 x i16]]]]]
@var_26 = external global i16
@var_27 = external global i64
@arr_38 = external global [16 x [10 x [24 x [10 x [10 x i64]]]]]
@arr_39 = external global [16 x [10 x [24 x [10 x [10 x i16]]]]]
@arr_40 = external global [16 x [10 x i16]]
@arr_41 = external global [16 x [10 x i64]]
@var_28 = external global i16
@var_29 = external global i32
@var_30 = external global i32

define i8 @test(i8 %arg, i8 %arg1, i32 %arg2, i8 %arg3, i32 %arg4, i8 %arg5, i8 %arg6, i8 %arg7, i8 %arg8, i8 %arg9, i8 %arg10, i8 %arg11, i8 %arg12, i8 %arg13, i16 %arg14, i8 %arg15, i64 %arg16, i32 %arg17, [11 x i32] %arg18, [11 x [11 x i16]] %arg19, [16 x [10 x i64]] %arg20, [16 x [10 x i8]] %arg21, [16 x [10 x [24 x i16]]] %arg22, [16 x [10 x [24 x [10 x i8]]]] %arg23, [16 x [10 x [24 x [10 x i16]]]] %arg24, [16 x [10 x [24 x [10 x i8]]]] %arg25, [16 x [10 x [24 x [10 x [21 x i32]]]]] %arg26, [16 x [10 x [24 x [10 x [21 x i16]]]]] %arg27, [16 x [10 x [24 x [10 x [21 x i8]]]]] %arg28, [16 x [10 x [24 x [10 x [14 x i32]]]]] %arg29) {
bb:
  br i1 undef, label %.critedge, label %.critedge14

.critedge:                                        ; preds = %.critedge, %bb
  br i1 undef, label %.critedge, label %.critedge14

.critedge14:                                      ; preds = %.critedge, %bb
  ret i8 0
}

declare i32 @min(...)

declare i32 @min.1(...)

declare i32 @max(...)

[rotateright]

I don't think this is a hang. It's just taking forever to create the SDAG because those global arrays are so big. If you replace with smaller constants, it should eventually finish compiling in a more reasonable time.

I don't know whether there's some non-linear behavior or other limit that could be imposed to make this compile faster.

[fime-sonia]

I want to take a look at this issue.