Issue 243047
Summary [flang] Compile time is cubic in the number of cases of an INTEGER SELECT CASE
Labels slow-compile, flang:fir-hlfir
Assignees
Reporter eugeneepshteyn
    Compile time for a SELECT CASE on an INTEGER selector grows roughly with the cube of the number of cases, even at -O0. A subroutine with 4000 cases takes about 2 minutes to compile with `flang -c -O0`; gfortran takes 0.2 s.

Generator (`python3 gen.py N > case_N.f90`):

```python
import sys
n = int(sys.argv[1])
print('subroutine s(n, r)')
print('  integer :: n, r')
print('  select case (n)')
for i in range(1, n + 1):
    print(f' case ({3 * i})')
    print(f'    r = {i}')
print('  end select')
print('end subroutine')
```

```console
python3 gen.py 2000 > case_2000.f90
flang -c -O0 -ftime-report case_2000.f90
```

Wall time (x86_64 Linux; flang built from main at 2f6c791287848c44fbfd85e724fd4f8728aad7d4, release with assertions; gfortran 13.3):

| cases | flang -c -O0 | flang -fc1 -emit-hlfir | gfortran -c -O0 |
|---|---|---|---|
| 1000 | 2.5 s | 1.1 s | |
| 2000 | 18.3 s | 7.4 s | 0.11 s |
| 4000 | 117.9 s | 46.6 s | 0.22 s |

flang 21.1.5 (release, no assertions) grows the same way (`-emit-hlfir`: 0.85 s, 5.5 s and 39.8 s), so this is not assertion overhead and is not recent.

With `-ftime-report` at 2000 cases, "MLIR generation" takes about 6 s and two SimplifyRegionLite runs take about 5 s each, out of about 17 s in total. Backtraces sampled during the compile are all in `mlir::runRegionDCE`, called once from lowering (`eraseDeadCodeAndBlocks` in `flang/lib/Lower/Bridge.cpp`) and once from each SimplifyRegionLite run:

- `propagateLiveness` calls `processValue` for each value, and `isUseSpeciallyKnownDead` calls `BranchOpInterface::getSuccessorBlockArgument(operandIndex)` for every use by a terminator. A `fir.select_case` with N cases has about N case-value operands.
- The default `getSuccessorBlockArgument` loops over all N+1 successors and calls `getSuccessorOperands(i)` for each one.
- For `fir.select_case`, `getSuccessorOperands(i)` is itself linear in `i`: `getSubOperands` in `FIROps.cpp` sums the first `i` entries of the target operand offsets, and `getMutableSuccessorOperands` calls `getAttrDictionary()` on every call.

That makes one liveness sweep O(N^3). In this example none of the successors takes block arguments, so the search never finds anything.

Possible directions: give the `fir.select*` ops their own `getSuccessorBlockArgument`, which can map an operand index to its successor with a single pass over the offsets, and make `getSuccessorOperands` compute an offset without rebuilding the attribute dictionary. The same helpers also back `fir.select`, `fir.select_rank` and `fir.select_type`.

Related but different: 236492 (CHARACTER cases at -O3, where the cost is in LLVM loop passes).

(This issue was filed with the help of AI)

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

Reply via email to