RFR: 8357781: Deep recursion in PhaseCFG::set_next_call leads to stack overflow

[Manuel Hässig]

On Mon, 26 May 2025 12:07:08 GMT, Marc Chevalier <mchevalier at openjdk.org> wrote:

> There is nothing very wrong here:
> - the graph is not broken
> - the algorithm is correct
> 
> It just happens that the graph is very deep, it has a very long, narrow chain of nodes because of crazy unrolling, because of `LoopUnrollLimit=8192`. This depth simply makes the algorithm recurse deeper than the stack size allows. This kind of graph shape is not quite trivial to reproduce. The proposed reproducer is very easy to change into a non-reproducer, with many kinds of change, even that seem harmless to me.
> 
> The fix is also pretty direct: let's change the recursive traversal, with a worklist-based iterative one. It's not as elegant, but it doesn't overflow.
> 
> How sad stacks are still so bounded...

Thanks for working on this fix, Marc. The conversion to a worklist-based loop looks good. I only found a few formatting nits.

src/hotspot/share/opto/lcm.cpp line 800:

> 798: void PhaseCFG::set_next_call(const Block* block, Node* init, VectorSet& next_call) const {
> 799:   Node_List worklist;
> 800:   worklist.push(init);

I guess the only reason `init` is not `const` is because of `Node_List::push()`?

src/hotspot/share/opto/lcm.cpp line 805:

> 803:     Node* n = worklist.pop();
> 804:     if (next_call.test_set(n->_idx)) continue;
> 805:     for (uint i=0; i < n->len(); i++) {

Suggestion:

    for (uint i = 0; i < n->len(); i++) {

Formatting nit

src/hotspot/share/opto/lcm.cpp line 807:

> 805:     for (uint i=0; i < n->len(); i++) {
> 806:       Node* m = n->in(i);
> 807:       if(m == nullptr) continue;  // must see all nodes in block that precede call

Suggestion:

      if (m == nullptr) continue;  // must see all nodes in block that precede call

Formatting nit

test/hotspot/jtreg/compiler/c2/StackOverflowInSetNextCall.java line 30:

> 28:  * @summary Triggered a stack overflow in PhaseCFG::set_next_call. The graph is legitimately big (mostly deep and not wide)
> 29:  *          which makes the old version of PhaseCFG::set_next_call crash.
> 30:  *

Suggestion:

 * @summary Triggered a stack overflow in PhaseCFG::set_next_call due to a legitimately big (mostly deep and not wide) graph.

A bit more concise. Feel free to ignore.

test/hotspot/jtreg/compiler/c2/StackOverflowInSetNextCall.java line 66:

> 64:     public static void main(String[] args) {
> 65:         for (int i = 0; i < 400; ++i) {
> 66:             test ();

Suggestion:

            test();

Formatting nit

-------------

Marked as reviewed by mhaessig (Author).

PR Review: https://git.openjdk.org/jdk/pull/25448#pullrequestreview-2870215197
PR Review Comment: https://git.openjdk.org/jdk/pull/25448#discussion_r2108603383
PR Review Comment: https://git.openjdk.org/jdk/pull/25448#discussion_r2108604728
PR Review Comment: https://git.openjdk.org/jdk/pull/25448#discussion_r2108605573
PR Review Comment: https://git.openjdk.org/jdk/pull/25448#discussion_r2108614005
PR Review Comment: https://git.openjdk.org/jdk/pull/25448#discussion_r2108608005