[Python-Dev] lnotab and the AST optimizer

[Thomas Lee]

Antoine Pitrou wrote:
> Hi,
>
>   
Hi. Thanks for getting back to me so quickly. I can even respond before 
I have to drag myself off to bed. :)

>> I'm making some good progress with the AST optimizer, and now the main 
>> thing standing in my way is lnotab. Currently lnotab expects bytecode 
>> sequencing to be roughly in-sync with the order of the source file and a 
>> few things that the optimizer does (e.g. swapping the bodies of an 
>> if/else after removing negation such that "if not X: A; else: B" becomes 
>> "if X: B; else A") breaks this assumption. This will result in either an 
>> assertion failure or incorrect line numbers being reported.
>>     
>
> In http://bugs.python.org/issue2459 ("speedup for / while / if with better
> bytecode") I had the same problem and decided to change the lnotab format so
> that line number increments are signed bytes rather than unsigned. The proposed
> patch contains many other changes, but with a bit of perseverance you may be
> able to extract the lnotab-related modifications... ;)
>
> This modification will allow many more types of control flow transformations
> than the current scheme does.
>
>   
Great, thanks! I'll check it out next week.
> By the way:
>   
>> swapping the bodies of an 
>> if/else after removing negation such that "if not X: A; else: B" becomes 
>> "if X: B; else A")
>>     
>
> Is this really an optimization? "if" and "if not" should use the same number of
> opcodes (the former produces JUMP_IF_FALSE and the latter JUMP_IF_TRUE).
>
>   

Not quite. :) Even if we were producing a JUMP_IF_FALSE, it'd still be 
nice to optimize away the UNARY_NOT in the former.

In practice, both actually produce a JUMP_IF_TRUE due to an existing 
optimization in the peephole optimizer which does just that. I'm trying 
to emulate this at the AST level because I'm part of a secret, evil 
conspiracy to be rid of the peephole optimizer. Shh. The relevant code 
in the peepholer, plus comment:

            /* Replace UNARY_NOT JUMP_IF_FALSE POP_TOP with
               with    JUMP_IF_TRUE POP_TOP */
            case UNARY_NOT:
                if (codestr[i+1] != JUMP_IF_FALSE  ||
                    codestr[i+4] != POP_TOP  ||
                    !ISBASICBLOCK(blocks,i,5))
                    continue;
                tgt = GETJUMPTGT(codestr, (i+1));
                if (codestr[tgt] != POP_TOP)
                    continue;
                j = GETARG(codestr, i+1) + 1;
                codestr[i] = JUMP_IF_TRUE;
                SETARG(codestr, i, j);
                codestr[i+3] = POP_TOP;
                codestr[i+4] = NOP;
                break;

A little hackage with the dis module seems to confirm this is the case.

Of course, if you know of a situation where this optimization doesn't 
apply and we actually wind up with a JUMP_IF_FALSE for an if/else 
post-peephole, I'm all ears.

Thanks again!

Cheers,
T