https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127094
Bug ID: 127094
Summary: Compile-time hogs with ranger and phis
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: compile-time-hog
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: ktkachov at gcc dot gnu.org
Target Milestone: ---
Created attachment 65429
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65429&action=edit
compile-time-hog reproducer
Attaching reproducer. With the help of an AI agent the analysis is:
The source creates this SSA shape:
```text
b_2 = PHI <0, 1, ..., N-1>
a_1 = PHI <b_2, b_2, ..., b_2, -1>
```
The input has O(N) PHI operands. Each distinct PHI should be scanned once.
`phi_analyzer::process_phi` is in `gcc/gimple-range-phi.cc:387` through `424`.
The analyzer marks a PHI in `m_current` only after it removes that PHI from
`m_work`.
When it scans `a_1` first, each repeated `b_2` argument pushes `b_2` because
`b_2` is not yet marked. The first `b_2` pop marks it and scans its N
arguments. Each duplicate pop scans the same N arguments again. The pop path
does not skip a PHI that is already in `m_current`. This gives approximately
N times N argument visits for O(N) input.
