Issue 244873
Summary [VPlan] Compile-time hang at -O3: exponential recursion in `vputils::isSingleScalar` from `narrowToSingleScalarRecipes`
Labels new issue
Assignees
Reporter haoxintu
    ## Description

```c
unsigned y;

void f(unsigned s1, unsigned i1)
{
  unsigned s2 = 0x5555u, i0;
  switch (y)
 {
    case 33:
      for (;;)
        {
          do
            {
 i1++;
              s2 ^= s2;
              i0 = 0;
 do
                {
                  i0++;
                  if ((s2 + s1) & 15)
                    {
                      unsigned t = y ^ s2;
                      s2 -= t ^ (t >> (t * 0x9e3779b9u & 31));
 }
                }
              while (i0 < 17u);
 }
          while (i1 < 5u);
        case 15:
          s1 -= s2;
 }
    }
}
```

```
$ time clang -O3 -c repro.c      # does not finish within 300 s
$ time clang -O2 -c repro.c      # 0.1 s
```

`-ftime-report` on a larger variant: LoopVectorizePass takes 127.5 s of 128.2 s. `opt -passes=loop-vectorize` on the IR before the vectorizer (`repro.ll`) does not finish within 60 s, and llvm 21.1.8's `opt` finishes it at once.

A stack sample shows unbounded recursion of `vputils::isSingleScalar` over the operands. It is called from `narrowToSingleScalarRecipes`:

```
llvm::vputils::isSingleScalar(llvm::VPValue const*)
std::__find_if<..., _Iter_negate<bool (*)(llvm::VPValue const*)>>(...)
llvm::vputils::isSingleScalar(llvm::VPValue const*)
... (repeated)
narrowToSingleScalarRecipes(llvm::VPlan&)
llvm::VPlanTransforms::optimize(llvm::VPlan&)
llvm::LoopVectorizationPlanner::buildVPlans(...)
llvm::LoopVectorizePass::processLoop(llvm::Loop*)
```

Reproduced in Godbolt (x86-64 clang assertions trunk, -O3): https://godbolt.org/z/e95aoMaWG (the compile times out there)

## Checked Versions

- Hangs at -O3 with clang trunk 2012344e5da8 (2026-11-19); -O0/-O1/-O2/-Os are fine.
- clang 21.1.8 compiles it at -O3 in under 1 s, so this is a regression.

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

Reply via email to