Skip to content

Fix literal_unroll pass erroneously exiting on non-conformant loop. - #8321

Merged
sklam merged 1 commit into
numba:mainfrom
stuartarchibald:fix/8311
Aug 17, 2022
Merged

Fix literal_unroll pass erroneously exiting on non-conformant loop.#8321
sklam merged 1 commit into
numba:mainfrom
stuartarchibald:fix/8311

Conversation

@stuartarchibald

@stuartarchibald stuartarchibald commented Aug 8, 2022

Copy link
Copy Markdown
Contributor

The guard code for checking a loop is conformant to what
literal_unroll can handle was incorrectly exiting the pass if it
encountered a non-conformant loop, e.g. a while loop, opposed to
just ignoring it.

Fixes #8311

@stuartarchibald
Fix literal_unroll pass erroneously exiting on non-conformant loop.
e89191b 
The guard code for checking a loop is conformant to what
literal_unroll can handle was incorrectly exiting the pass if it
encountered a non-conformant loop, e.g. a while loop, opposed to
just ignoring it.

Fixes numba#8311
@stuartarchibald
stuartarchibald marked this pull request as ready for review August 8, 2022 09:47
@stuartarchibald
stuartarchibald requested a review from sklam as a code owner August 8, 2022 09:47
@stuartarchibald stuartarchibald mentioned this pull request Aug 8, 2022
Closed
2 tasks done
@esc esc added this to the Numba 0.57 RC milestone Aug 9, 2022
gmarkall
gmarkall reviewed Aug 17, 2022
View reviewed changes

@gmarkall gmarkall left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think I'm ready to approve this, but I first want to confirm my understanding of the issue and patch is correct. I have resisted understanding entirely how the literal unroll pass works in detail, because there's a lot to it, but my general understanding is that it unrolls the loop and generates a switch table on the type of the "current" item containing the loop body so it can be typed for each member type as appropriate.

Anyway, I think what happened was:

  • On the first iteration of applying the transform in MixedContainerUnroller.run_pass(), apply_transform() runs, transforms the literal_unroll() loop, and then moves on to looking at the while loop.
  • It sees that the while loop is not in the correct form for a literal unroll, so it returns False
  • Back in run_pass, stat gets set to False, and therefore mutated does too, and the iteration of applying the transform exits its "infinite loop".
  • The function was changed, but run_pass returns False and signals that it did not change anything, and chaos ensues from the resulting inconsistency.

With the fix, the big for loop in apply_transform carries on looking at all loops even if some of them aren't in a suitable form for transformation, and therefore correctly reports that a change was made, so the subsequent pipeline operations get a consistent / correct view of things.

If this is accurate then I think the fix and test are good. If it's inaccurate I'll have another attempt at understanding the situation 🙂

@gmarkall gmarkall added 4 - Waiting on author Waiting for author to respond to review and removed 3 - Ready for Review labels Aug 17, 2022
@stuartarchibald

stuartarchibald commented Aug 17, 2022

Copy link
Copy Markdown
Contributor Author

I think I'm ready to approve this, but I first want to confirm my understanding of the issue and patch is correct. I have resisted understanding entirely how the literal unroll pass works in detail, because there's a lot to it, but my general understanding is that it unrolls the loop and generates a switch table on the type of the "current" item containing the loop body so it can be typed for each member type as appropriate.

Anyway, I think what happened was:

* On the first iteration of applying the transform in `MixedContainerUnroller.run_pass()`, `apply_transform()` runs, transforms the `literal_unroll()` loop, and then moves on to looking at the `while` loop.

* It sees that the `while` loop is not in the correct form for a literal unroll, so it returns `False`

* Back in `run_pass`, `stat` gets set to `False`, and therefore `mutated` does too, and the iteration of applying the transform exits its "infinite loop".

* The function was changed, but `run_pass` returns `False` and signals that it did not change anything, and chaos ensues from the resulting inconsistency.

With the fix, the big for loop in apply_transform carries on looking at all loops even if some of them aren't in a suitable form for transformation, and therefore correctly reports that a change was made, so the subsequent pipeline operations get a consistent / correct view of things.

If this is accurate then I think the fix and test are good. If it's inaccurate I'll have another attempt at understanding the situation slightly_smiling_face

Thanks for taking a look at this @gmarkall. I think your description is close to my assessment, but I think the root cause comes from this large loop:

numba/numba/core/untyped_passes.py

Lines 1039 to 1132 in a06693d

for lbl, loop in loops.items():
# TODO: check the loop head has literal_unroll, if it does but
# does not conform to the following then raise
# scan loop header
iternexts = [_ for _ in
func_ir.blocks[loop.header].find_exprs('iternext')]
if len(iternexts) != 1:
return False
for iternext in iternexts:
# Walk the canonicalised loop structure and check it
# Check loop form range(literal_unroll(container)))
phi = guard(get_definition, func_ir, iternext.value)
if phi is None:
continue
# check call global "range"
range_call = guard(get_call_args, phi.value, range)
if range_call is None:
continue
range_arg = range_call.args[0]
# check call global "len"
len_call = guard(get_call_args, range_arg, len)
if len_call is None:
continue
len_arg = len_call.args[0]
# check literal_unroll
literal_unroll_call = guard(get_definition, func_ir, len_arg)
if literal_unroll_call is None:
continue
if not isinstance(literal_unroll_call, ir.Expr):
continue
if literal_unroll_call.op != "call":
continue
literal_func = getattr(literal_unroll_call, 'func', None)
if not literal_func:
continue
call_func = guard(get_definition, func_ir,
literal_unroll_call.func)
if call_func is None:
continue
call_func = call_func.value
if call_func is literal_unroll:
assert len(literal_unroll_call.args) == 1
arg = literal_unroll_call.args[0]
typemap = state.typemap
resolved_arg = guard(get_definition, func_ir, arg,
lhs_only=True)
ty = typemap[resolved_arg.name]
assert isinstance(ty, self._accepted_types)
# loop header is spelled ok, now make sure the body
# actually contains a getitem
# find a "getitem"
tuple_getitem = None
for lbl in loop.body:
blk = func_ir.blocks[lbl]
for stmt in blk.body:
if isinstance(stmt, ir.Assign):
if (isinstance(stmt.value, ir.Expr) and
stmt.value.op == "getitem"):
# check for something like a[i]
if stmt.value.value != arg:
# that failed, so check for the
# definition
dfn = guard(get_definition, func_ir,
stmt.value.value)
if dfn is None:
continue
try:
args = getattr(dfn, 'args', False)
except KeyError:
continue
if not args:
continue
if not args[0] == arg:
continue
target_ty = state.typemap[arg.name]
if not isinstance(target_ty,
self._accepted_types):
continue
tuple_getitem = stmt
break
if tuple_getitem:
break
else:
continue # no getitem in this loop
ui = unroll_info(loop, literal_unroll_call, arg,
tuple_getitem)
literal_unroll_info[lbl] = ui

doing a scan of all loops to build up some analysis info into variable literal_unroll_info about the "literal_unroll" driven loops. The bug is that this analysis loop exits the entire function here if a non-conformant loop is found:

numba/numba/core/untyped_passes.py

Lines 1046 to 1047 in a06693d

if len(iternexts) != 1:
return False

which means there's no transformation made, hence the literal_unroll pass has no effect and the getitem on a heterogeneous tuple still exists which leads to the typing error.

@stuartarchibald stuartarchibald added 4 - Waiting on reviewer Waiting for reviewer to respond to author and removed 4 - Waiting on author Waiting for author to respond to review labels Aug 17, 2022
@gmarkall

gmarkall commented Aug 17, 2022

Copy link
Copy Markdown
Member

Ah, that explanation makes the error message make way more sense. The only way I could rationalise it was that something inconsistent made a lot of confusion down the line. Thanks for clarifying!

gmarkall
gmarkall approved these changes Aug 17, 2022
View reviewed changes

@gmarkall gmarkall left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks good to me, now that I understand the issue properly! 🙂

@gmarkall gmarkall 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 Aug 17, 2022
@stuartarchibald

stuartarchibald commented Aug 17, 2022

Copy link
Copy Markdown
Contributor Author

Ah, that explanation makes the error message make way more sense. The only way I could rationalise it was that something inconsistent made a lot of confusion down the line. Thanks for clarifying!

No problem. Thanks for the assessment and review.

@sklam
sklam merged commit ada94f4 into numba:main Aug 17, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@gmarkall gmarkall gmarkall approved these changes
@sklam sklam Awaiting requested review from sklam

Assignees

@gmarkall gmarkall

Labels

5 - Ready to merge Review and testing done, is ready to merge Effort - short Short size effort needed

Projects

None yet

Milestone

Numba 0.57 RC

Development

Successfully merging this pull request may close these issues.

presence of while loop breaks literal_unroll compilation

4 participants

@stuartarchibald @gmarkall @esc @sklam