[Python-Dev] lnotab and the AST optimizer
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. It seems that lnotab is used in relatively few places in the source code at the moment, but if I'm going to make a change to how lnotab works I want to do so in a way that's going to allow me to move forward while keeping everybody happy. I'm away for a few days so I probably won't be able to get back to anybody until either Sunday or Monday, but I'd appreciate it if anybody in the know can weigh in on this. Cheers, Tom ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Hi, 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. 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). Regards Antoine. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Antoine Pitrou solipsis at pitrou.net writes: 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. By the way, the same change could be done for relative jump offsets in the bytecode (change them from unsigned shorts to signed shorts). Taken together, both modifications would release a lot of constraints on the ordering of code blocks. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
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 withJUMP_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 ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Antoine Pitrou wrote: Antoine Pitrou solipsis at pitrou.net writes: 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. By the way, the same change could be done for relative jump offsets in the bytecode (change them from unsigned shorts to signed shorts). Taken together, both modifications would release a lot of constraints on the ordering of code blocks. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/tom%40vector-seven.com By the way, you were right about JUMP_IF_TRUE/JUMP_IF_FALSE. It's far too late. Apologies. I'm still pretty sure this is the peepholer's doing, though, and if that's the case then I want to try and deal with it at the AST level. Which is what's being achieved with the AST optimization I originally proposed, right? Cheers, T ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Thomas Lee tom at vector-seven.com writes: By the way, you were right about JUMP_IF_TRUE/JUMP_IF_FALSE. It's far too late. Apologies. I'm still pretty sure this is the peepholer's doing, Yes indeed. Which is what's being achieved with the AST optimization I originally proposed, right? Well, not exactly, your optimization eliminates the UNARY_NOT by swapping the if/else blocks, while the peepholer eliminates the UNARY_NOT by fusing it with the subsequent jump opcode. In this case it doesn't make much of a difference, but if there is only an if without an else, the peepholer's optimization is still possible while yours is not. (bottom line: the peepholer is not dead!) cheers, Antoine. ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Antoine Pitrou wrote: Thomas Lee tom at vector-seven.com writes: By the way, you were right about JUMP_IF_TRUE/JUMP_IF_FALSE. It's far too late. Apologies. I'm still pretty sure this is the peepholer's doing, Yes indeed. Which is what's being achieved with the AST optimization I originally proposed, right? Well, not exactly, your optimization eliminates the UNARY_NOT by swapping the if/else blocks, while the peepholer eliminates the UNARY_NOT by fusing it with the subsequent jump opcode. In this case it doesn't make much of a difference, but if there is only an if without an else, the peepholer's optimization is still possible while yours is not. Unless a pass is injected into the if body, which will generate no additional bytecode and still have the same net effect. (bottom line: the peepholer is not dead!) We'll see ;) Thanks for all your help, I'm looking forward to getting my hands on that patch. Cheers, T ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
At 12:56 AM 7/25/2008 +1000, Thomas Lee wrote: 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. It seems that lnotab is used in relatively few places in the source code at the moment, but if I'm going to make a change to how lnotab works I want to do so in a way that's going to allow me to move forward while keeping everybody happy. I'm away for a few days so I probably won't be able to get back to anybody until either Sunday or Monday, but I'd appreciate it if anybody in the know can weigh in on this. I'd personally love it if the lnotab were capable of handling line numbers from different files as well as out-of-order lines. (For function inlining, among other more esoteric things.) ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] lnotab and the AST optimizer
Thomas Lee wrote: I'm making some good progress with the AST optimizer, and now the main thing standing in my way is lnotab. My suggestion would be to drop the idea of trying to compress the lnotab in clever ways, and just make it a straightforward list of bytecode offset/line number pairs. I can't imagine that the size of an uncompressed lnotab would be a problem in this day and age. If ordering is an issue, generate it internally as a dict and convert it to a sorted list on output. -- Greg ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
