classification
Title: conditional jump to a POP_TOP optimization
Type: Stage:
Components: Interpreter Core Versions: Python 3.0, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: _doublep, georg.brandl, jackdied, pitrou, rhettinger
Priority: normal Keywords: patch

Created on 2008-03-09 15:35 by _doublep, last changed 2008-11-18 00:07 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
jump-to-pop-optimization.diff _doublep, 2008-03-09 15:35
pop_peep.diff rhettinger, 2008-11-16 14:27 POP JMP 1 POP optimization
Messages (10)
msg63422 - (view) Author: Paul Pogonyshev (_doublep) Date: 2008-03-09 15:35
This optimization targets a common case of functions like this:

def foo(a, b):
    if a:
        if b:
            return 'true'

Before the optimization:
  6           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE           16 (to 22)
              6 POP_TOP

  7           7 LOAD_FAST                1 (b)
             10 JUMP_IF_FALSE            5 (to 18)
             13 POP_TOP

  8          14 LOAD_CONST               1 ('true')
             17 RETURN_VALUE
        >>   18 POP_TOP
             19 JUMP_FORWARD             1 (to 23)
        >>   22 POP_TOP
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE

After:
  6           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE           16 (to 22)
              6 POP_TOP

  7           7 LOAD_FAST                1 (b)
             10 JUMP_IF_FALSE            9 (to 22)
             13 POP_TOP

  8          14 LOAD_CONST               1 ('true')
             17 RETURN_VALUE
             18 POP_TOP
             19 JUMP_FORWARD             1 (to 23)
        >>   22 POP_TOP
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE

Note that size of bytecode doesn't become smaller, however one execution
branch (jump from offset 10) becomes shorter by one JUMP_FORWARD.  

Additionally, two commands at offset 18 become unreachable.  However,
they will not be removed by the patch in issue1394 currently, because
there is a basic-block change at 18, where JUMP_IF_FALSE previously had
its target.  If we want unreachable code be removed in such cases, we
need to make peepholer make two passes with recomputing blocks[] in
between.  This would enable more optimizations.
msg63424 - (view) Author: Paul Pogonyshev (_doublep) Date: 2008-03-09 15:39
Also, this is the reason for while() in the patch.  Consider this function:

def bar(a, b, c):
    if a:
        if b:
            if c:
                return 'true'

Before the patch:
 11           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE           27 (to 33)
              6 POP_TOP

 12           7 LOAD_FAST                1 (b)
             10 JUMP_IF_FALSE           16 (to 29)
             13 POP_TOP

 13          14 LOAD_FAST                2 (c)
             17 JUMP_IF_FALSE            5 (to 25)
             20 POP_TOP

 14          21 LOAD_CONST               1 ('true')
             24 RETURN_VALUE
        >>   25 POP_TOP
             26 JUMP_ABSOLUTE           34
        >>   29 POP_TOP
             30 JUMP_FORWARD             1 (to 34)
        >>   33 POP_TOP
        >>   34 LOAD_CONST               0 (None)
             37 RETURN_VALUE

After:
 11           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE           27 (to 33)
              6 POP_TOP

 12           7 LOAD_FAST                1 (b)
             10 JUMP_IF_FALSE           20 (to 33)
             13 POP_TOP

 13          14 LOAD_FAST                2 (c)
             17 JUMP_IF_FALSE           13 (to 33)
             20 POP_TOP

 14          21 LOAD_CONST               1 ('true')
             24 RETURN_VALUE
             25 POP_TOP
             26 JUMP_ABSOLUTE           34
             29 POP_TOP
             30 JUMP_FORWARD             1 (to 34)
        >>   33 POP_TOP
        >>   34 LOAD_CONST               0 (None)
             37 RETURN_VALUE

Without the while(), target for jump at offset 17 wouldn't be optimized,
because "jump to unconditional jump" optimization hasn't been done yet:
it is farther in the code.
msg70540 - (view) Author: Jack Diederich (jackdied) * (Python committer) Date: 2008-08-01 03:43
+0

* The peepholer comment promises "Optimizations are restricted to simple
transformations occuring within a single basic block." and this goes
beyond that.  You could patch that comment.
* This needs a matching patch to Lib/test/test_peepholer.py
* Deeply nested "if"s suffer a flat penalty because the unconditional
jump peepholer figures this out after the first extra POP_TOP (notice
the JUMP_ABSOLUTE in your second disassembly).
* I noticed the NOP assignment is commented out in your patch, was that
unsafe?

I searched for old threads on the peephole optimizer and came up with these:
Skip Montanaro's paper
  http://www.webfast.com/~skip/python/spam7/optimizer.html
Two old python-dev threads
  http://www.gossamer-threads.com/lists/python/dev/645669
  http://www.gossamer-threads.com/lists/python/dev/645669

I was hoping to find out if writing a bytecode optimizer in python had
been discussed because a generic version of your optimization would be
really easy to write in pure python (using a dict for the jump table,
for instance).  I found nothing;  my search terms might have been
insufficient.
msg70546 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-08-01 09:41
While this patch is interesting, I think it would be more efficient to
introduce variants of JUMP_IF_FALSE and JUMP_IF_TRUE which pop their
argument rather than leaving it on the stack (like I did in #2459).
msg75935 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-16 12:51
This looks fine to me.  Go ahead and uncomment the memcpy() line (I
presume you commented it out in order to demonstrate the basic
transformation without the dead code elimination).  Be sure to add a
testcase.

Antoine, the issue with JUMP_IF variants is that they interfere with
other existing byte code optimizations, resulting in a net loss.

BTW, don't expect much of a real-world speed-up from this patch.  The
JUMP_ABSOLUTE opcode is very fast.
msg75936 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-11-16 13:08
> Antoine, the issue with JUMP_IF variants is that they interfere with
> other existing byte code optimizations, resulting in a net loss.

Which other byte code optimizations does it interfere with?
msg75937 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-16 13:13
Am taking this one back.  May have a simpler approach.
msg75938 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-16 14:27
Adding a simpler approach.  It's a bit limited because some common cases
have the POP_TOP JUMP_FORWARD 1 pair split across two basic blocks. 
Those cases should not be optimized away on a first pass.
msg75944 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-16 21:13
Georg, would you please give this a second review.  It passes the whole
test suite for me and triggers often.
msg75994 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-11-18 00:07
Applied simplified patch r67253 .
History
Date User Action Args
2008-11-18 00:07:59rhettingersetstatus: open -> closed
assignee: georg.brandl ->
resolution: fixed
messages: + msg75994
2008-11-16 21:13:10rhettingersetassignee: rhettinger -> georg.brandl
messages: + msg75944
nosy: + georg.brandl
2008-11-16 14:27:02rhettingersetfiles: + pop_peep.diff
messages: + msg75938
2008-11-16 13:13:50rhettingersetassignee: rhettinger
messages: + msg75937
2008-11-16 13:08:41pitrousetmessages: + msg75936
2008-11-16 12:51:48rhettingersetassignee: rhettinger -> (no value)
messages: + msg75935
versions: + Python 3.0, Python 2.7
2008-08-01 09:41:22pitrousetnosy: + pitrou
messages: + msg70546
2008-08-01 08:28:01rhettingersetassignee: rhettinger
nosy: + rhettinger
2008-08-01 03:43:15jackdiedsetnosy: + jackdied
messages: + msg70540
2008-03-09 15:39:37_doublepsetmessages: + msg63424
2008-03-09 15:35:59_doublepcreate