Issue 242910
Summary [SelectionDAG][ARM] Thumb-1: `ScheduleDAGRRList` spends seconds to minutes in `IsChainDependent` on one basic block (compile-time blow-up)
Labels new issue
Assignees
Reporter haradama
    ### Summary

On `thumbv6m` one basic block with a few 64-bit variable shifts (libcalls on Thumb-1) and a run of interleaved stores and loads takes 5.4 s in `llc -O2`; the function it was reduced from takes 115 s (0.1 s for `thumbv7m`). All of the time is in "Instruction Scheduling", inside the recursive `IsChainDependent` in `ScheduleDAGRRList.cpp`. The same inputs compile in 0.03 s for `thumbv7m`, where the shifts are inline and no call sequence is being scheduled.

### Reproducer

`repro.ll` is attached below (107 lines, `llvm-reduce` output with a ">1.5 s" criterion).

```
$ time llc -O2 -mtriple=thumbv6m-none-eabi repro.ll -o /dev/null
real	0m5.4s
$ time llc -O2 -mtriple=thumbv7m-none-eabi repro.ll -o /dev/null
real	0m0.03s
```

`-time-passes` (LLVM 22.1.7):

```
                      Instruction Selection and Scheduling
   5.3890 (100.0%)   0.0000 (  0.0%)   5.3890 (100.0%)   5.3890 (100.0%)  Instruction Scheduling
```

Interrupting `llc` under gdb at three different moments gives the same picture each time — a deep recursion of one function:

```
#0  IsChainDependent(llvm::SDNode*, llvm::SDNode*, unsigned int, llvm::TargetInstrInfo const*)
#1  IsChainDependent(llvm::SDNode*, llvm::SDNode*, unsigned int, llvm::TargetInstrInfo const*)
#2  IsChainDependent(llvm::SDNode*, llvm::SDNode*, unsigned int, llvm::TargetInstrInfo const*)
...
```

### Observations

- The block's only calls are the two shift libcalls (`__aeabi_llsl`, `__aeabi_llsr`), so `IsChainDependent` is being asked whether one call sequence is chain-reachable from the other while the first is being scheduled.
- My reading of the stack (not verified against the source): `IsChainDependent` recurses into the operands of `TokenFactor` nodes without remembering what it has visited, so a chain graph in which `TokenFactor`s share predecessors is walked once per path rather than once per node.
- The time is a cliff, not a slope, in this input: the block has seven `store i64 0` / `load i16` pairs before the shifts; with all seven it takes 5.4 s, and removing the first of them (or more) brings it to 0.03 s. I was not able to turn it into a clean parametric family (four hand-written attempts at "N diamonds between two libcalls" all compiled instantly), so the reduced real input is what I have.
- `-O0` on the same input: 1.0 s; `-O1`: 5.4 s.
- Possibly related: #40609 (quadratic behaviour in the same scheduler's `popFromQueueImpl`), though the hot function here is a different one.

### Version

LLVM 22.1.7 (`llc --version`: "LLVM version 22.1.7, Optimized build"). I have not tested trunk.

<details>
<summary>repro.ll</summary>

```llvm
target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "thumbv6m-unknown-none-eabi"

define void @f(i1 %0, ptr %1, ptr %2, ptr %3, i1 %.inv99.not, i64 %4, ptr %5, i16 %6) {
  %8 = alloca [17 x i64], align 8
  br label %._crit_edge

._crit_edge:                                      ; preds = %._crit_edge, %7
  br i1 %0, label %._crit_edge, label %.preheader74.preheader

.preheader74.preheader:                           ; preds = %._crit_edge
  %9 = alloca [17 x i16], align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %9, align 2
  store i16 0, ptr %2, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %3, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr null, align 2
  %10 = getelementptr i8, ptr %5, i32 14
  store i16 0, ptr %10, align 2
  store i16 0, ptr %5, align 2
  %11 = getelementptr i8, ptr %5, i32 18
  store i16 0, ptr %11, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr null, align 2
  store i16 0, ptr %3, align 2
  store i16 0, ptr %2, align 2
  store i16 0, ptr %1, align 2
  store i16 0, ptr %2, align 2
  %12 = getelementptr i8, ptr %9, i32 32
  store i16 0, ptr %12, align 2
  store i64 0, ptr %8, align 8
  %13 = load i16, ptr null, align 2
  %14 = getelementptr i8, ptr %8, i32 8
  store i64 0, ptr %14, align 8
  %15 = load i16, ptr null, align 2
  %16 = getelementptr i8, ptr %8, i32 16
  store i64 0, ptr %16, align 8
  %17 = load i16, ptr null, align 2
  %18 = getelementptr i8, ptr %8, i32 24
  store i64 0, ptr %18, align 8
  %19 = load i16, ptr null, align 2
  %20 = getelementptr i8, ptr %8, i32 32
  store i64 0, ptr %20, align 8
  %21 = load i16, ptr null, align 2
  %22 = getelementptr i8, ptr %8, i32 40
  store i64 0, ptr %22, align 8
  %23 = load i16, ptr null, align 2
  %24 = getelementptr i8, ptr %8, i32 48
  store i64 0, ptr %24, align 8
  %25 = load i16, ptr null, align 2
  %26 = getelementptr i8, ptr %8, i32 104
  store i64 0, ptr %26, align 8
  %27 = load i16, ptr null, align 2
  %28 = load i16, ptr %1, align 2
  %29 = sext i16 %28 to i32
  %30 = sext i16 %27 to i32
  %31 = mul i32 %29, %30
  %32 = sext i32 %31 to i64
  store i64 %32, ptr null, align 8
  %33 = load i16, ptr null, align 2
  %34 = load i16, ptr %1, align 2
  %35 = sext i16 %34 to i32
  %36 = sext i32 %35 to i64
  store i64 %36, ptr null, align 8
  %37 = load i16, ptr null, align 2
  %38 = load i16, ptr %1, align 2
  store i64 0, ptr null, align 8
  %39 = load i64, ptr %2, align 8
  %40 = sext i16 %38 to i32
  %41 = sext i32 %40 to i64
  %42 = load i64, ptr %1, align 8
  %43 = select i1 %.inv99.not, i64 %42, i64 0
  store i64 %43, ptr %1, align 8
  %.inv99.not1 = icmp eq i64 %41, 0
  %44 = load i64, ptr %2, align 8
  %45 = select i1 %.inv99.not1, i64 %44, i64 0
  store i64 %45, ptr null, align 8
  store i64 0, ptr %2, align 8
  store i64 %39, ptr %1, align 8
  store i64 0, ptr %2, align 8
  %46 = load i64, ptr %1, align 8
  %47 = select i1 %0, i64 %46, i64 0
  %48 = load i64, ptr %3, align 8
  %49 = shl i64 %48, %4
  %50 = select i1 %.inv99.not, i64 %49, i64 0
  %51 = alloca [17 x i16], align 2
  %52 = ashr i64 1, %4
  %53 = trunc i64 %52 to i16
  store i16 %53, ptr %1, align 2
  %54 = select i1 %.inv99.not, i64 0, i64 %4
  %55 = trunc i64 %54 to i16
  store i16 %55, ptr %51, align 2
  %56 = trunc i64 %50 to i16
  store i16 %56, ptr %2, align 2
  %57 = trunc i64 %47 to i16
  store i16 %57, ptr null, align 2
  ret void

}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
```

</details>

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to