simple patch, improving unreachable bytecode removing

@gvanrossum

BPO	1394
Nosy	@gvanrossum, @rhettinger, @abalkin, @benjaminp
Files	unreachable-code.diff test_peepholer.diff unreachable-code-1.diff: diff against revision 61073 unreachable-code-with-tests.diff: diff against revision 61073

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2008-06-24.23:20:57.417>
created_at = <Date 2007-11-05.22:09:01.645>
labels = ['interpreter-core']
title = 'simple patch, improving unreachable bytecode removing'
updated_at = <Date 2008-06-24.23:20:57.408>
user = 'https://bugs.python.org/doublep'

bugs.python.org fields:

activity = <Date 2008-06-24.23:20:57.408>
actor = 'gvanrossum'
assignee = 'none'
closed = True
closed_date = <Date 2008-06-24.23:20:57.417>
closer = 'gvanrossum'
components = ['Interpreter Core']
creation = <Date 2007-11-05.22:09:01.645>
creator = '_doublep'
dependencies = []
files = ['8699', '9555', '9556', '9559']
hgrepos = []
issue_num = 1394
keywords = ['patch']
message_count = 19.0
messages = ['57141', '62953', '62964', '62992', '62999', '63000', '63004', '63005', '63006', '63017', '63019', '63020', '63029', '63040', '63043', '63045', '63046', '68709', '68710']
nosy_count = 6.0
nosy_names = ['gvanrossum', 'nnorwitz', 'rhettinger', 'belopolsky', '_doublep', 'benjamin.peterson']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue1394'
versions = ['Python 2.6']

This patch improves bytecode output, by removing unreachable code. It
doesn't target special cases, as now, but provides a generic implementation.

I am not sure what this patch would accomplish. I tried
$ cat t.py
def f():
return 1
1+2
from dis import dis
print dis(f)

Both with and without patch I get

$ ./python.exe -O t.py
  2           0 LOAD_CONST               1 (1)
              3 RETURN_VALUE

3 4 LOAD_CONST 1 (1)
7 LOAD_CONST 2 (2)
10 BINARY_ADD
11 POP_TOP
None

I am sure I am missing something, but it is hard to tell what without
any use cases provided.

It would be great to see test cases with this change. That would help
answer Alexander's question too.

I figured that out:

>>> def g():
...   raise RuntimeError
...

Before the patch:

>>> dis(g)
  2           0 LOAD_GLOBAL              0 (RuntimeError)
              3 RAISE_VARARGS            1
              6 LOAD_CONST               0 (None)
              9 RETURN_VALUE        

After the patch:
>>> dis(g)
  2           0 LOAD_GLOBAL              0 (RuntimeError)
              3 RAISE_VARARGS            1

Looks reasonable to me. Paul, do you need help with unit tests?

Yes, help with unit tests would be appreciated. Especially since it is
not supposed to fix anything, so I'm not sure what unit tests should be
like...

BTW, trying to understand why the patch didn't remove unreachable code
in your first example, I noticed this (both cases are with patch):

def f1():
    return 1
    x()

disassembly:
3 0 LOAD_CONST 1 (1)
3 RETURN_VALUE

4 4 LOAD_GLOBAL 0 (x)
7 CALL_FUNCTION 0
10 POP_TOP

def f2():
    return 1
    x()
    return 2

disassembly:
3 0 LOAD_CONST 1 (1)
3 RETURN_VALUE

Looking a bit further, I noticed this:
if (codestr[codelen-1] != RETURN_VALUE)
goto exitUnchanged;

So, the patch really can't help with your first example, because peephol
optimizer just bails out before real action begins.

Speaking of which, I propose that codestr[] array is made one byte
longer and RETURN_VALUE opcode wrote in that extra byte. It will be
removed by this patch anyway (if it is accepted), but we'll remove a way
to accidentally disable peephole optimizer.

I mean, it would cost almost nothing, yet will prevent making some
functions non-optimized. E.g. like this:

def foo(x):
    if x >= 0:
        return x * 2
    raise ValueError

Yes, help with unit tests would be appreciated. Especially since it is
not supposed to fix anything, so I'm not sure what unit tests should be
like...
Unit tests are just for bugfixes. They let us make sure Python is doing
what we want it to do in a given case. Your unit test will probably have
functions where you optimization should take effect and assert that it
does. For starters, take a look at Lib/test/test_peephole.py

On Mon, Feb 25, 2008 at 1:32 PM, Benjamin Peterson
<report@bugs.python.org> wrote:

Unit tests are just for bugfixes.

I presume you meant "are *not* just for bugfixes".

I presume you meant "are *not* just for bugfixes".
(Sigh) Yes, of course.

Attached patch adds test_elim_unreachable() unit test. Last two
assertions should fail with unpatched python.

I am still trying to convince myself that the transformation are
correct.

I propose that codestr[] array is made one byte
longer and RETURN_VALUE opcode wrote in that extra byte.

I don't think that will be correct. Did you consider the following
comment?

    /* Verify that RETURN_VALUE terminates the codestring.  This

allows
the various transformation patterns to look ahead several
instructions without additional checks to make sure they are
not
looking beyond the end of the code string.
*/
if (codestr[codelen-1] != RETURN_VALUE)
goto exitUnchanged;

Thanks for writing the test.

Yes, I did read the comment. As I understood it, RETURN_VALUE is needed
only so that various optimization can assume codestr[] cannot suddenly
end without one. E.g. if you match for BINARY_ADD, you can safely check
the next command: if BINARY_ADD matched, there is a _guaranteed_ next
command, not an out-of-array failure.

Such proposed fake RETURN_VALUE _must_ be unreachable, so it must not be
problematic at all. If it was reachable, real codestr[] would end in
reachable non-return command, which must not happen during compilation.
I dunno, maybe interpreter guards against execution point falling of
the bytecode string, but in any case this must not happen in
non-corrupted files generated by the bytecode compiler.

Paul,

You are right. I misunderstood that comment myself. I've tried the
attached modification to your patch (unreachable-code-1.diff) and it
passes all tests while fixing msg62953 problem:

$ cat t.py 
def f():
    return 1
    1+2
from dis import dis
dis(f)

$ ./python.exe t.py
  6           0 LOAD_CONST               0 (None)
              3 RETURN_VALUE

Can you add more tests? It seems that almost all the examples given in
this thread are good examples. Also something like:

  while 1:
    if cond: return 1
    return 2
  return 3

There are a bunch more cases that could be added for where the code
should be optimized or might be optimized wrong that.

The #if 0 code should be removed in the patch. Also, since
CONTINUE_LOOP is removed in this patch, it would be good to explicitly
add a test for that.

This patch looks good to me, but I'll let Raymond decide. Did all the
entire test suite run? Note, you must remove all the .pyc files to test
this patch or change the MAGIC number in Python/import.c.

I have added more tests as Neal suggested. See unreachable-code-with-
tests.diff for a combined patch. I've rerun all tests after removing
.pyc files and also with -O option (ensuring no existing .pyo files as
well). All works.

I've removed #if 0 block and changed "Verify" to "Ensure" in the
RETURN_VALUE comment. Paul, maybe you and add an explanation why the
added RETURN_VALUE will always be eliminated. I am not sure when python
produces code with no terminating RETURN_VALUE in the first place.

Well, I cannot guarantee it will _always_ be eliminated, since I too
don't really know when generated bytecode can (currently) end in
non-return. However, if before it ended in non-return, that non-return
must have been unreachable, obviously (else code flow would fall off of
the valid bytecode string). So, there is pretty good chance that this
patch will remove both the unreachable code and the fake return byte.
In the worst case, we increase bytecode length by 1 byte, but we always
enable peephole optimizer, which can be expected to give a much more
significant gain.

As your unit tests suggest, the patch doesn't always remove unreachable
code, because some opcodes after which this can be done are already
handled differently. Also, there might in theory be some false block
boundaries (e.g. a jump from unreachable code to another piece of such
code).

BTW, I think that just removing #if 0'd block is not correct. I propose
to convert it to a comment then, just to explain that there are more
opcodes after which we can expect unreachable code and don't check only
because it'd give duplicate case labels. Maybe some goto magic can
handle them, don't have sources here.

Actually, it is even better. Since you don't increment codelen, that
extra RETURN_VALUE is "virtual" in that it acts as a sentinel, but will
not appear in the resulting bytecode. You can test this by backing out
the patch and disassembling something. For this reason, if() before
writing the RETURN_VALUE is not needed.

Since you don't increment codelen ..

Good catch!

For this reason, if() before
writing the RETURN_VALUE is not needed.

In this case it will be clearer to use STOP_CODE instead of RETURN_VALUE
as a sentinel.

Recommend rejecting. Too much work for zero performance payoff.

Rejecting. Too much risk as well, based on experience in the past with
supposedly harmless optimizations.

Navigation Menu

Repository navigation

simple patch, improving unreachable bytecode removing #45735

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

simple patch, improving unreachable bytecode removing #45735

Description

Activity

doublep commented on Nov 5, 2007

abalkin commented on Feb 25, 2008

nnorwitz commented on Feb 25, 2008

abalkin commented on Feb 25, 2008

doublep commented on Feb 25, 2008

doublep commented on Feb 25, 2008

benjaminp commented on Feb 25, 2008

gvanrossum commented on Feb 25, 2008

benjaminp commented on Feb 25, 2008

abalkin commented on Feb 25, 2008

doublep commented on Feb 26, 2008

abalkin commented on Feb 26, 2008

nnorwitz commented on Feb 26, 2008

abalkin commented on Feb 26, 2008

doublep commented on Feb 26, 2008

doublep commented on Feb 26, 2008

abalkin commented on Feb 26, 2008

rhettinger commented on Jun 24, 2008

gvanrossum commented on Jun 24, 2008

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions