| 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