Improper inlining of function in loop condition

[DWesl]

Given this input:

def is_even(n: int) -> int:
    return (n & 1) == 0

#pythran export trailing_zero_bits(int)
def trailing_zero_bits(n: int) -> int:
    result = 0
    while is_even(n):
        n >>= 1
        result += 1
    return result

pythran -P produces

def is_even(n):
    return ((n & 1) == 0)
def trailing_zero_bits(n):
    n_ = n
    result = 0
    __pythran_inlineis_evenn0 = n_
    while ((__pythran_inlineis_evenn0 & 1) == 0):
        n_ >>= 1
        result += 1
    return result

The problem is the creation of the __pythran_inlineis_evenn0, specifically the loop whose condition it is used in.

I suspect this catches a corner case on the function inliner: to avoid duplicate side effects from evaluating an expression every place the argument appears in the inlined function, it creates a variable to hold the value of that expression, assigns that value to that variable on the previous line, and uses the new variable in the inlined function body.

If the function is used anywhere other than an elif or while condition, this works very well. If it occurs in an elif condition, one need merely move the assignment before the corresponding if (and ensure there are no name collisions with functions inlined in the if or preceeding elif conditions) or separate out elif into else and if, providing a space for the assignment to happen between the two.

If a function is to be inlined into a while condition, the assignment must be duplicated: placed not merely on the previous line, but also as the last line of the while loop body. It seems pythran 0.17.0, at least on Cygwin, does not perform that second assignment.

I don't know enough of the pythran internals to be sure where in the optimizers the inliner lives, nor with Python ASTs to be able to insert the second assignment at the required location.

[DWesl]

After poking at the syntax tree a bit, it looks like the inliner is looking for function calls, and doesn't have a way to see if they're in a condition or not (no links to parent nodes).

The next-best thing I can think of would be changing the visit_While function a few lines earlier to see if its test is an inlinable Call and adding the relevant assignments to the end of the body. If the visits are performed in postorder rather than preorder, it might be possible to steal the assignment information from the already-visited Call node.

With pre-order, at least the inliner replaces the to-be-inlined function, so it might be a matter of performing a manual visit, checking to see if the result changes, taking the new assignments from the updated Call node's defs attribute, appending those assignments to the While node's body, and updating the While node's test attribute.

Given the way the tree seems to be constructed, it's most likely a postorder visit, which means storing the assignments in the new expression node in a manner the While node can check for and extract to append to its body. The Call node has this information, but it gets replaced by whatever expression nodes was in the Returns node of its function's body.

[DWesl]

Ah, I forgot about continue. I think the only method to make this work without going absurdly deep is to avoid inlining functions in the conditions of while loops. The only exception would be for calls using only bare variables and numeric literals as arguments (or collections of those, but that's much harder to check).

With pre-order visits, it would be possible to set a flag to avoid inlining. With postorder visits, I think you'd need a pass primarily to note which nodes are in the condition of a while loop. Fortunately, while-loop conditions are usually short enough that the duplicate work on the test won't affect too much.

I think this might be a complete test case, with test_function2 being test_function with is_even inlined using close to the current scheme:

def is_even(n: int) -> bool:
    return (n % 2) == 0

def test_function(n: int) -> int:
    result = 0
    while is_even(n):
        if n % 3 == 1:
            n //= 3
            if n % 5 == 3:
                continue
        n //= 4
        length += 1
    return length

def test_function2(n):
    result = 0
    _n = n
    while _n % 2 == 0:
        if n % 3 == 1:
            n //= 3
            if n % 5 == 3:
                _n = n
                continue
        n //= 4
        length += 1
        _n = n
    return length

This would be much simpler if nobody could nest ifs.

[DWesl]

Perhaps a previous pass to turn

while condition1:
    if condition2:
        do_stuff()
        continue
    do_things()

into

while condition1:
    if condition2:
        do_stuff()
    else:
        do_things()

would help? At least then there's only two places that execute condition1 next.

[serge-sans-paille]

Thanks for reporting the issue! I'll have a look once I'm done with #2281 which had a bigger impact than what I thought :-)

[serge-sans-paille]

#2288 prevents inlining in the case of a while test. A better approach would be to use the cfg analysis to compute predecessors and insert definitions at each predecessor, but I don't have time to rework the pass to to this now. But maybe you're interested to give it a try? The import analysis is https://github.com/serge-sans-paille/pythran/blob/master/pythran/analyses/cfg.py