fix `RecursionError` on large, generated CFGs by esc · Pull Request #10482 · numba/numba

esc · 2026-03-16T11:58:23Z

We convert the recursive implementation of the _find_topo_order function to a stack based one. This fixes previously encountered issues when attempting to compile large synthetically generated programs. The Control Flow Graph of these programs would become so large that this implementation would hit the Python interpreter recursion limit.

esc · 2026-03-16T12:05:19Z

This can be tested with the reproducer:

from numba import njit
import numpy as np


def generate_code(count):
    base_code = """
    dependency_{index} = 1 if True else 0
    value_{index} = x if dependency_{index} else 0"""

    code = """
@njit
def template(x):"""
    for i in range(count):
        code += base_code.format(**{'index': i})
    return code

if __name__ == '__main__':
    import sys
    import time

    count = int(sys.argv[1])

    exec(generate_code(count), globals(), locals())
    start = time.time()
    template(32)
    end = time.time()
    print(end - start, 'elapsed')

Running:

python repro.py 512

Will yield a recursion error without this PR:

esc@artemis [numba_3.14] [numba:main:★★₃] ~/git/numba python ~/git/numba-issues/numba/5611/repro.py 512
Traceback (most recent call last):
  File "/Users/esc/git/numba-issues/numba/5611/repro.py", line 25, in <module>
    template(32)
    ~~~~~~~~^^^^
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 443, in _compile_for_args
    raise e
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 376, in _compile_for_args
    return_val = self.compile(tuple(argtypes))
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 908, in compile
    cres = self._compiler.compile(args, return_type)
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 80, in compile
    status, retval = self._compile_cached(args, return_type)
                     ~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 94, in _compile_cached
    retval = self._compile_core(args, return_type)
  File "/Users/esc/git/numba/numba/core/dispatcher.py", line 107, in _compile_core
    cres = compiler.compile_extra(self.targetdescr.typing_context,
                                  self.targetdescr.target_context,
    ...<2 lines>...
                                  flags=flags, locals=self.locals,
                                  pipeline_class=self.pipeline_class)
  File "/Users/esc/git/numba/numba/core/compiler.py", line 739, in compile_extra
    return pipeline.compile_extra(func)
           ~~~~~~~~~~~~~~~~~~~~~~^^^^^^
  File "/Users/esc/git/numba/numba/core/compiler.py", line 439, in compile_extra
    return self._compile_bytecode()
           ~~~~~~~~~~~~~~~~~~~~~~^^
  File "/Users/esc/git/numba/numba/core/compiler.py", line 505, in _compile_bytecode
    return self._compile_core()
           ~~~~~~~~~~~~~~~~~~^^
  File "/Users/esc/git/numba/numba/core/compiler.py", line 481, in _compile_core
    raise e
  File "/Users/esc/git/numba/numba/core/compiler.py", line 473, in _compile_core
    pm.run(self.state)
    ~~~~~~^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 363, in run
    raise e
  File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 356, in run
    self._runPass(idx, pass_inst, state)
    ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/compiler_lock.py", line 35, in _acquire_compile_lock
    return func(*args, **kwargs)
  File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 311, in _runPass
    mutated |= check(pss.run_pass, internal_state)
               ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 272, in check
    mangled = func(compiler_state)
  File "/Users/esc/git/numba/numba/core/untyped_passes.py", line 249, in run_pass
    main, withs = transforms.with_lifting(
                  ~~~~~~~~~~~~~~~~~~~~~~~^
        func_ir=state.func_ir,
        ^^^^^^^^^^^^^^^^^^^^^^
    ...<3 lines>...
        locals=state.locals,
        ^^^^^^^^^^^^^^^^^^^^
    )
    ^
  File "/Users/esc/git/numba/numba/core/transforms.py", line 396, in with_lifting
    withs, func_ir = find_setupwiths(func_ir)
                     ~~~~~~~~~~~~~~~^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/transforms.py", line 592, in find_setupwiths
    with_ranges_dict = find_ranges(blocks)
  File "/Users/esc/git/numba/numba/core/transforms.py", line 554, in find_ranges
    for setup_block in cfg.topo_sort(sus_setups, reverse=True):
                       ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 318, in topo_sort
    it = self._topo_order
         ^^^^^^^^^^^^^^^^
  File "/Users/esc/miniconda3/envs/numba_3.14/lib/python3.14/functools.py", line 1127, in __get__
    val = self.func(instance)
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 220, in _topo_order
    return self._find_topo_order()
           ~~~~~~~~~~~~~~~~~~~~~^^
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 655, in _find_topo_order
    _dfs_rec(self._entry_point)
    ~~~~~~~~^^^^^^^^^^^^^^^^^^^
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec
    _dfs_rec(dest)
    ~~~~~~~~^^^^^^
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec
    _dfs_rec(dest)
    ~~~~~~~~^^^^^^
  File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec
    _dfs_rec(dest)
    ~~~~~~~~^^^^^^
  [Previous line repeated 975 more times]
RecursionError: maximum recursion depth exceeded

Question: should we include the reproducer as a test?

As title Assisted-by: Claude Sonnet 4.6.

As title

As title Authored-by: Claude Sonnet 4.6.

sklam · 2026-03-23T22:44:06Z

+        # 6a. The fixed functions must NOT appear in the traceback.
+        cfg_overflow_frames = [
+            f for f in tb_frames
+            if "controlflow" in f.filename
+            and f.name in ("_find_topo_order", "_dfs_rec")
+        ]
+        self.assertFalse(
+            cfg_overflow_frames,
+            msg=(
+                f"RecursionError originated in "
+                f"controlflow.{cfg_overflow_frames[0].name} — "
+                f"the iterative fix for _topo_order is not active.\n\n"
+                f"Full traceback:\n"
+                + "".join(traceback.format_tb(caught_exc.__traceback__))
+            ) if cfg_overflow_frames else "",
+        )
+
+        # 6b. The overflow must have come from SSA processing, confirming
+        #     the CFG phase completed without hitting the stack limit.
+        ssa_frames = [
+            f for f in tb_frames
+            if "ssa" in f.filename.lower()
+        ]
+        self.assertTrue(
+            ssa_frames,
+            msg=(
+                "Expected the RecursionError to originate in SSA processing "
+                "(numba/core/ssa.py), but no SSA frames appear in the "
+                "traceback.  The overflow may have come from an unexpected "
+                "location.\n\nTraceback:\n"
+                + "".join(traceback.format_tb(caught_exc.__traceback__))
+            ),
+        )
+


This part seems to allow a silent passing of the test even if the RecursionError is raised as _find_topo_order and _dfs_rec are already removed. So assertFalse(cfg_overflow_frames) will always pass.

Can we just rely on caught_exc is None early exit?

Yes, I thought about that some more too. Originally, the idea was to check that the recursion error was due a regression, i.e. _find_topo_order has become recursive again. This request was raised by @stuartarchibald OOB. However, maybe it suffices to just early exit if we see any kind of recursion error and then a developer will need to look at the cause. I think the chances of this fix regressing is fairly slim, so there is little value in trying to determine the cause of the RecursionError programmatically. I will simplify.

I've now done this in ff822f9. The error on main looks like:

esc@artemis [numba_3.11] [numba:main:★★₄] ~/git/numba python -m numba.runtests -v numba.tests.test_controlflow test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ... FAIL ====================================================================== FAIL: test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ---------------------------------------------------------------------- Traceback (most recent call last): File "/Users/esc/git/numba/numba/tests/support.py", line 698, in inner self.subprocess_test_runner( File "/Users/esc/git/numba/numba/tests/support.py", line 679, in subprocess_test_runner self.assertEqual(status.returncode, 0, streams) AssertionError: 1 != 0 : captured stdout: captured stderr: F ====================================================================== FAIL: test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ---------------------------------------------------------------------- Traceback (most recent call last): File "/Users/esc/git/numba/numba/tests/support.py", line 709, in inner func(self) File "/Users/esc/git/numba/numba/tests/test_controlflow.py", line 144, in test_topo_order_no_recursion_in_large_cfg self.fail(msg) AssertionError: Unexpected RecursionError.Potential regression related to fiding toplogical order. Full traceback: File "/Users/esc/git/numba/numba/tests/test_controlflow.py", line 126, in test_topo_order_no_recursion_in_large_cfg njit(ns["_large_cfg_func"])(1) File "/Users/esc/git/numba/numba/core/dispatcher.py", line 443, in _compile_for_args raise e File "/Users/esc/git/numba/numba/core/dispatcher.py", line 376, in _compile_for_args return_val = self.compile(tuple(argtypes)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/dispatcher.py", line 908, in compile cres = self._compiler.compile(args, return_type) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/dispatcher.py", line 80, in compile status, retval = self._compile_cached(args, return_type) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/dispatcher.py", line 94, in _compile_cached retval = self._compile_core(args, return_type) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/dispatcher.py", line 107, in _compile_core cres = compiler.compile_extra(self.targetdescr.typing_context, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler.py", line 739, in compile_extra return pipeline.compile_extra(func) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler.py", line 439, in compile_extra return self._compile_bytecode() ^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler.py", line 505, in _compile_bytecode return self._compile_core() ^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler.py", line 481, in _compile_core raise e File "/Users/esc/git/numba/numba/core/compiler.py", line 473, in _compile_core pm.run(self.state) File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 363, in run raise e File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 356, in run self._runPass(idx, pass_inst, state) File "/Users/esc/git/numba/numba/core/compiler_lock.py", line 35, in _acquire_compile_lock return func(*args, **kwargs) ^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 311, in _runPass mutated |= check(pss.run_pass, internal_state) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/compiler_machinery.py", line 272, in check mangled = func(compiler_state) ^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/untyped_passes.py", line 249, in run_pass main, withs = transforms.with_lifting( ^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/transforms.py", line 396, in with_lifting withs, func_ir = find_setupwiths(func_ir) ^^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/transforms.py", line 592, in find_setupwiths with_ranges_dict = find_ranges(blocks) ^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/transforms.py", line 554, in find_ranges for setup_block in cfg.topo_sort(sus_setups, reverse=True): File "/Users/esc/git/numba/numba/core/controlflow.py", line 318, in topo_sort it = self._topo_order ^^^^^^^^^^^^^^^^ File "/Users/esc/miniconda3/envs/numba_3.11/lib/python3.11/functools.py", line 1001, in __get__ val = self.func(instance) ^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/controlflow.py", line 220, in _topo_order return self._find_topo_order() ^^^^^^^^^^^^^^^^^^^^^^^ File "/Users/esc/git/numba/numba/core/controlflow.py", line 655, in _find_topo_order _dfs_rec(self._entry_point) File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec _dfs_rec(dest) File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec _dfs_rec(dest) File "/Users/esc/git/numba/numba/core/controlflow.py", line 652, in _dfs_rec _dfs_rec(dest) [Previous line repeated 30 more times] File "/Users/esc/git/numba/numba/core/controlflow.py", line 650, in _dfs_rec for dest in succs[node]: ~~~~~^^^^^^ ---------------------------------------------------------------------- Ran 1 test in 0.112s FAILED (failures=1) ---------------------------------------------------------------------- Ran 1 test in 0.468s FAILED (failures=1)

esc · 2026-03-24T12:48:13Z

It seems like the determination of the bszie isn't too stable. Even with a factor of 2 (so, the recursion limit is set to bsize * 2) to allow for sufficient headroom, we still get an issue with:

  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  [Previous line repeated 1 more time]

So effectively, the use of sys.setrecursionlimit with a limit that is too low means that the compilation will fail, because there is a bunch of recursion going on in _abc_subclasscheck(cls, subclass). I think the problem here is that the trivial compile used to determine bszie doesn't pick up on this, perhaps because the compilation is too trivial?

esc · 2026-03-24T13:32:18Z

It seems like the determination of the bszie isn't too stable. Even with a factor of 2 (so, the recursion limit is set to bsize * 2) to allow for sufficient headroom, we still get an issue with:
  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  File "C:\Miniconda\envs\testenv\lib\abc.py", line 123, in __subclasscheck__
    return _abc_subclasscheck(cls, subclass)
  [Previous line repeated 1 more time]
So effectively, the use of sys.setrecursionlimit with a limit that is too low means that the compilation will fail, because there is a bunch of recursion going on in _abc_subclasscheck(cls, subclass). I think the problem here is that the trivial compile used to determine bszie doesn't pick up on this, perhaps because the compilation is too trivial?

Oh, looks like there was a git issue, doing bszie * 2 is actually fine.

As title

esc · 2026-03-24T13:56:10Z

@siu I've fixed up the headroom and addressed the issue you raised. Can you please re-review.

As title

esc · 2026-03-24T18:02:15Z

@jc-5s : have a look at this one. I found an even better way to eliminate the RecursionError. Turns out all the code was there already and just had to be re-used. 🎉

sklam · 2026-03-24T20:01:25Z

+    With 2 ternaries per iteration this creates roughly 6–8 CFG blocks
+    per iteration, so count=100 gives ~600–800 nodes — sufficient to


This is not correct estimation of nodes. The graph from _generate_large_cfg_source(100) has 200-300 nodes.

OK, I deleted the comments in 61b63ea

sklam · 2026-03-24T20:10:34Z

+            pairs (~600–800 CFG nodes).  The old recursive _dfs_rec
+            would have needed ~600–800 extra frames — well over Bsize —


These facts on CFG nodes is not true.

Oh, ok. Deleted the comment in 557dabe

sklam · 2026-03-24T20:10:37Z

+    finally:
+        CFGraph.process = orig_process   # always restore
+
+    return depth_sample[0]


CFtGraph.process doesn't call topo_order, which is ran lazily as needed. It makes more sense to intercept topo_order to get the actual stack depth when it is first invoked for a compilation.

Using the following diff I get:

commit 2256d54a13ee3e5398d76ef9b5b0d1794be0d541 (HEAD -> fix/5611/cfg_recursion) Author: Emergency Self-Construct <esc@users.noreply.github.com> Date: Tue Mar 24 22:00:21 2026 +0100 intercept topo_order instead As title diff --git a/numba/tests/test_controlflow.py b/numba/tests/test_controlflow.py index 30c9fbba1b..55b88ad0a5 100644 --- a/numba/tests/test_controlflow.py +++ b/numba/tests/test_controlflow.py @@ -50,7 +50,7 @@ def _measure_trivial_compile_depth(): O(calls × depth) like settrace, so it is fast. """ depth_sample = [0] - orig_process = CFGraph.process + orig_process = CFGraph.topo_order def _probing_process(self): f = sys._getframe() @@ -62,7 +62,7 @@ def _measure_trivial_compile_depth(): depth_sample[0] = d return orig_process(self) - CFGraph.process = _probing_process + CFGraph.topo_order = _probing_process try: @njit def _trivial(x):

I get:

esc@artemis [numba_3.14] [numba:fix/5611/cfg_recursion:★★₄:»] ~/git/numba python -m numba.runtests -v numba.tests.test_controlflow test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ... FAIL ====================================================================== FAIL: test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ---------------------------------------------------------------------- Traceback (most recent call last): File "/Users/esc/git/numba/numba/tests/support.py", line 698, in inner self.subprocess_test_runner( ~~~~~~~~~~~~~~~~~~~~~~~~~~~^ test_module=self.__module__, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...<4 lines>... _subproc_test_env=func.__name__, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ) ^ File "/Users/esc/git/numba/numba/tests/support.py", line 679, in subprocess_test_runner self.assertEqual(status.returncode, 0, streams) ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ AssertionError: 1 != 0 : captured stdout: captured stderr: E ====================================================================== ERROR: test_topo_order_no_recursion_in_large_cfg (numba.tests.test_controlflow.TestCFGTopoOrderNonRecursive.test_topo_order_no_recursion_in_large_cfg) ---------------------------------------------------------------------- Traceback (most recent call last): File "/Users/esc/git/numba/numba/tests/support.py", line 709, in inner func(self) ~~~~^^^^^^ File "/Users/esc/git/numba/numba/tests/test_controlflow.py", line 109, in test_topo_order_no_recursion_in_large_cfg sys.setrecursionlimit(Bsize) ~~~~~~~~~~~~~~~~~~~~~^^^^^^^ ValueError: recursion limit must be greater or equal than 1 ---------------------------------------------------------------------- Ran 1 test in 0.054s FAILED (errors=1) ---------------------------------------------------------------------- Ran 1 test in 0.409s FAILED (failures=1)

sklam · 2026-03-24T20:17:05Z

+                ),
+                ns,
+            )
+            njit(ns["_large_cfg_func"])(1)


The test here is very indirect. Given how CFGraph is lazily computing things, I'd suggest a more direct testing of the changed features by getting the CFGraph like below:

from numba.core.controlflow import ControlFlowAnalysis from numba.core.bytecode import FunctionIdentity, ByteCode def create_cfg_from_function(func): """Create a CFGraph from a Python function for direct testing.""" func_id = FunctionIdentity.from_function(func) bc = ByteCode(func_id) cfa = ControlFlowAnalysis(bc) cfa.run() return cfa.graph # Simple test function def simple_func(x): if x > 0: return x + 1 else: return x - 1 # Complex test function with many branches def complex_func(x): dep_0 = 1 if True else 0 val_0 = x if dep_0 else 0 dep_1 = 1 if True else 0 val_1 = x if dep_1 else 0 return x # Create CFGraphs for testing simple_cfg = create_cfg_from_function(simple_func) complex_cfg = create_cfg_from_function(complex_func) print(f"Simple CFG nodes: {len(simple_cfg._nodes)}") print(f"Complex CFG nodes: {len(complex_cfg._nodes)}")

Not sure about this, can you please outline what the intention is here? The test uses something similar to the original reproducer and checks for a RecursionError. I am not sure what CFG features you want tested? Do you want to use create_cfg_from_function to create a function using the reproducer? And then wrap the try except around a call to topo_order?

The intention is to be more direct in the testing. What you noted in #10482 (comment) is showing that topo_order is never used. It is an issue caused by the indirect testing:

the baseline stack depth measurement is for process

topo_order didn't execute in baseline

So it's better to test directly on the topo_order by manually and expliciting invoking that function. What I shown in the example snippet is how you can get hold of the CFGraph for a function.

Optionally, to make the testing more thorough and defensive against CFGraph functions becoming recursive. You can exercise the CFGraph functions one by one on pathological cases with a low recursion limit.

As title

esc · 2026-03-26T14:05:50Z

@sklam I implemented what you suggested OOB -- now using a much more direct approach to testing going on _topo_order. Both for determining the bszie and also for triggering the recursion error itself.

As title

sklam · 2026-03-26T19:39:28Z

+            f = _generate_large_cfg_source(100)
+            ns = {}
+            exec(
+                compile(
+                    f,
+                    "<generated_large_cfg>",
+                    "exec",
+                ),
+                ns,
+            )
+            c = _create_cfg_from_function(ns["_large_cfg_func"])


Only the c.topo_order() call should be affected by the recursion limit. All these lines should be moved before the setrecursionlimit(). Once I move it, it doesn't need the * 2 at (Bsize = int(depth_at_cfg_process * 2.0)) for extra headroom on my machine.

sklam · 2026-03-26T19:41:39Z

+            # Fail
+            msg = (
+                "Unexpected RecursionError."
+                "Potential regression related to fiding toplogical order.\n\n"


Suggested change

"Potential regression related to fiding toplogical order.\n\n"

"Potential regression related to finding toplogical order.\n\n"

As title

esc · 2026-03-26T20:32:09Z

@sklam I made the changes you requested (and fixed up the docs some more) -- but it seems like the current variant does not fail on main. I will need to take a look at this.

As title

JonAnCla · 2026-03-27T17:26:30Z

Nice! Thanks very much for finishing this off and sorry I wasn't able to come back to it. Much appreciated :)

esc · 2026-03-27T17:30:35Z

@JonAnCla thank you, for providing the initial patches!

Numba PR #10482 fixed #5611 by deriving topological order from an iterative postorder traversal instead of recursive DFS. Port that design to the vendored Numba core. NCM already has an iterative _find_postorder implementation, so reuse it rather than duplicating the traversal or copying upstream's replacement. Retaining the local helper also avoids upstream's seen-on-push behavior, which can emit invalid reverse postorder when DAG branches converge. The regression constructs a 2000-diamond graph under a low recursion limit and verifies every edge in the returned order. Fixes #11 Derived from: numba/numba#10482 Upstream issue: numba/numba#5611

esc added skip_release_notes Skip towncrier requirement 3 - Ready for Review labels Mar 16, 2026

esc mentioned this pull request Mar 16, 2026

Improve CFG algo performance for #5611 #10381

Closed

esc mentioned this pull request Mar 16, 2026

Control flow graph algorithm error when using many ternary operations #5611

Closed

2 tasks done

guilhermeleobas previously approved these changes Mar 16, 2026

View reviewed changes

esc dismissed guilhermeleobas’s stale review via a81d4da March 17, 2026 15:49

esc force-pushed the fix/5611/cfg_recursion branch from a81d4da to f9e18f2 Compare March 17, 2026 19:27

esc added 4 - Waiting on author Waiting for author to respond to review and removed 3 - Ready for Review labels Mar 18, 2026

esc force-pushed the fix/5611/cfg_recursion branch from 704ece8 to 0317552 Compare March 21, 2026 15:43

esc added 3 commits March 23, 2026 21:46

fixup the postorder implementation to avoid dual stack usage

7c161d4

As title Assisted-by: Claude Sonnet 4.6.

add all variation of potential topo order to test

fd7d26c

As title

adding tests

6adccab

As title Authored-by: Claude Sonnet 4.6.

esc force-pushed the fix/5611/cfg_recursion branch from 5d07b53 to 947a7cc Compare March 23, 2026 20:51

esc changed the title ~~Convert _find_topo_order from recursive implementation to stack based~~ fix RecursionError on large, generated CFGs Mar 23, 2026

sklam reviewed Mar 23, 2026

View reviewed changes

Fixup Claude generated code and docs to match reality

37352ad

As title

esc force-pushed the fix/5611/cfg_recursion branch from b24aa48 to 37352ad Compare March 24, 2026 13:33

simplify error detection

113e6b6

As title

esc force-pushed the fix/5611/cfg_recursion branch from ff822f9 to 113e6b6 Compare March 24, 2026 14:04

esc requested review from guilhermeleobas and sklam March 24, 2026 14:11

esc mentioned this pull request Mar 24, 2026

Accelerate CFG processing #10494

Merged

sklam requested changes Mar 24, 2026

View reviewed changes

esc requested a review from sklam March 24, 2026 21:08

esc added the 4 - Waiting on reviewer Waiting for reviewer to respond to author label Mar 24, 2026

esc added 2 commits March 24, 2026 22:15

remove incorrect comments

61b63ea

As title

intercept topo_order instead

717adcc

As title

esc force-pushed the fix/5611/cfg_recursion branch from 557dabe to 717adcc Compare March 24, 2026 21:15

esc added 2 commits March 26, 2026 13:37

enable more direct testing

3094e0b

As title

compile and exec function

717c501

As title

flake8 fixes

70f31e9

As title

sklam reviewed Mar 26, 2026

View reviewed changes

esc added 2 commits March 26, 2026 21:29

address review: move code outside of recursion limit reduction

027e960

As title

fixup docs some more

7e322f9

As title

esc added 7 commits March 27, 2026 13:26

fixups

e12402e

As title

probe on _find_topo_order

c2e0dc7

As title

fix test input size

fee6591

As title

simplify diff, move _find_topo_order to original location

6f69ae5

As title

fixup docs

9f7f7e1

As title

remove empty line at end of file

4390643

As title

add frame_depth to bszie

f48cd37

As title

sklam approved these changes Mar 27, 2026

View reviewed changes

sklam added 5 - Ready to merge Review and testing done, is ready to merge and removed 4 - Waiting on reviewer Waiting for reviewer to respond to author labels Mar 27, 2026

sklam merged commit 5b81fbd into numba:main Mar 27, 2026
26 checks passed

esc deleted the fix/5611/cfg_recursion branch March 30, 2026 09:19

This was referenced Aug 28, 2026

Compute CFGraph topological order without recursion ccam80/numba-cuda-mlir#13

Closed

Compute CFGraph topological order without recursion NVIDIA/numba-cuda-mlir#293

Merged

		With 2 ternaries per iteration this creates roughly 6–8 CFG blocks
		per iteration, so count=100 gives ~600–800 nodes — sufficient to

		pairs (~600–800 CFG nodes). The old recursive _dfs_rec
		would have needed ~600–800 extra frames — well over Bsize —

	"Potential regression related to fiding toplogical order.\n\n"
	"Potential regression related to finding toplogical order.\n\n"

Conversation

esc commented Mar 16, 2026

Uh oh!

esc commented Mar 16, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

esc commented Mar 24, 2026

Uh oh!

esc commented Mar 24, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

esc commented Mar 24, 2026

Uh oh!

esc commented Mar 24, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

esc Mar 24, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

esc commented Mar 26, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

esc commented Mar 26, 2026

Uh oh!

Uh oh!

JonAnCla commented Mar 27, 2026

Uh oh!

esc commented Mar 27, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

esc commented Mar 24, 2026 •

edited

Loading

esc Mar 24, 2026 •

edited

Loading