[Python-Dev] lnotab and the AST optimizer (original) (raw)

Thomas Lee tom at vector-seven.com
Thu Jul 24 17:49:37 CEST 2008

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 JUMPIFFALSE and the latter JUMPIFTRUE).

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

More information about the Python-Dev mailing list