RecursionError in parfor prelowering

[sklam]

Reporting a bug

• I have tried using the latest released version of Numba (most recent is
  visible in the change log (https://github.com/numba/numba/blob/main/CHANGE_LOG).
• I have included a self contained code sample to reproduce the problem.
  i.e. it's possible to run as 'python bug.py'.

Original discourse thread: https://numba.discourse.group/t/maximum-recursion-depth-exceeded-while-using-prange/2107

Reproducer:

1. Get pyreason:

   git clone https://github.com/lab-v2/pyreason
   cd pyreason
   git checkout 80fac257a0981cd758927b8c0232f2c37451976d
   pip install .
   

2. Use Numba: b96eab1

3. Run this script:

   from pyreason.scripts.interpretation.interpretation_parallel import _ground_node_rule
   from numba.types import DictType, unicode_type, UniTuple, ListType, boolean
   from pyreason.scripts.numba_wrapper.numba_types.rule_type import RuleType
   from pyreason.scripts.numba_wrapper.numba_types.world_type import WorldType
   
   Rule = RuleType()
   World = WorldType()
   bool = boolean
   
   _ground_node_rule.compile(
       (Rule, DictType(unicode_type, World), DictType(UniTuple(unicode_type, 2), World), ListType(unicode_type), DictType(unicode_type, ListType(unicode_type)), DictType(unicode_type, ListType(unicode_type)), bool, bool, ListType(unicode_type))
   )

RecursionError is coming from

numba/numba/parfors/parfor.py

Lines 3830 to 3833 in b96eab1

	def lookup(var, varonly=True):
	val = defs.get(var.name, None)
	if isinstance(val, ir.Var):
	return lookup(val)

because there is a cycle in defs. Printing var.name in lookup() shows:

....
clause_var_1.5
clause_var_1.6
clause_var_1.7
clause_var_1.3
clause_var_1.4
clause_var_1.5
clause_var_1.6
clause_var_1.7
clause_var_1.3
clause_var_1.4
clause_var_1.5
clause_var_1.6
clause_var_1.7
clause_var_1.3
clause_var_1.4
clause_var_1.5

Source for _ground_node_rule is at https://github.com/lab-v2/pyreason/blob/80fac257a0981cd758927b8c0232f2c37451976d/pyreason/scripts/interpretation/interpretation_parallel.py#L720. The function is complicated and I suspect the problem requires such complicated function to appear.

[sklam]

CC @DrTodd13

[sklam]

I have a minimized reproducer that does not use PyReason:

import numba
from numba import prange
from numba.types import ListType, Tuple, intp


@numba.njit
def _sink(x):
    pass


@numba.njit(cache=False, parallel=True)
def _ground_node_rule(
    clauses,
    nodes,
):
    for piter in prange(len(nodes)):
        for clause in clauses:
            clause_type = clause[0]
            clause_variables = clause[2]
            if clause_type == 0:
                clause_var_1 = clause_variables[0]
            elif len(clause_variables) == 2:
                clause_var_1, clause_var_2 = (
                    clause_variables[0],
                    clause_variables[1],
                )

            elif len(clause_variables) == 4:
                pass

            if clause_type == 1:
                _sink(clause_var_1)
                _sink(clause_var_2)


_ground_node_rule.compile(
    (
        ListType(Tuple([intp, intp, ListType(intp)])),
        ListType(intp),
    )
)

[sklam]

@DrTodd13, I hacked around the problem with sklam@19296a8 but I don't know if there's a deeper problem that I am just patching over; e.g. there is no reduction here.

[DrTodd13]

@sklam Indeed, there is no reduction there. Right now, we look for reductions among the variables that cross the parfor boundary. These are the parfor params. In this case, in the Python source you don't see clause_var_1 outside the prange but Numba seems to be inserting clause_var_1 = null() in the IR before the parfor and so it is being treated as input to the parfor. I think this is the core of the problem. I'm not sure if this cyclic dependency can happen in a true reduction case so not sure your patch is useful.

[DrTodd13]

Hi @sklam . I've been thinking about this one and I had some ideas and explored them but in the end didn't like them. The solution you wrote here seems a reasonable workaround. Can you just make a PR out of your solution and ask for my review?

[sklam]

PR opened at #9244