From fd2d1f7870ec5cd639ab7867a33c6f8628ca1dfb Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Mon, 23 Aug 2004 23:37:48 +0000 Subject: SF Patch #1013667: Cleanup Peepholer Output * Make a pass to eliminate NOPs. Produce code that is more readable, more compact, and a tiny bit faster. Makes the peepholer more flexible in the scope of allowable transformations. * With Guido's okay, bumped up the magic number so that this patch gets widely exercised before the alpha goes out. --- Lib/test/test_dis.py | 2 - Lib/test/test_peepholer.py | 104 ++++++++++++++++++++++++++++++++++ Python/compile.c | 135 +++++++++++++++++++++++++++++++++------------ Python/import.c | 3 +- 4 files changed, 206 insertions(+), 38 deletions(-) create mode 100644 Lib/test/test_peepholer.py diff --git a/Lib/test/test_dis.py b/Lib/test/test_dis.py index 6d5e054..985c878 100644 --- a/Lib/test/test_dis.py +++ b/Lib/test/test_dis.py @@ -18,8 +18,6 @@ dis_f = """\ %-4d 5 LOAD_CONST 1 (1) 8 RETURN_VALUE - 9 LOAD_CONST 0 (None) - 12 RETURN_VALUE """%(_f.func_code.co_firstlineno + 1, _f.func_code.co_firstlineno + 2) diff --git a/Lib/test/test_peepholer.py b/Lib/test/test_peepholer.py new file mode 100644 index 0000000..6c1900d --- /dev/null +++ b/Lib/test/test_peepholer.py @@ -0,0 +1,104 @@ +import dis +import sys +from cStringIO import StringIO +import unittest + +def disassemble(func): + f = StringIO() + tmp = sys.stdout + sys.stdout = f + dis.dis(func) + sys.stdout = tmp + result = f.getvalue() + f.close() + return result + +def dis_single(line): + return disassemble(compile(line, '', 'single')) + +class TestTranforms(unittest.TestCase): + + def test_unot(self): + # UNARY_NOT JUMP_IF_FALSE POP_TOP --> JUMP_IF_TRUE POP_TOP' + def unot(x): + if not x == 2: + del x + asm = disassemble(unot) + for elem in ('UNARY_NOT', 'JUMP_IF_FALSE'): + self.assert_(elem not in asm) + for elem in ('JUMP_IF_TRUE', 'POP_TOP'): + self.assert_(elem in asm) + + def test_elim_inversion_of_is_or_in(self): + for line, elem in ( + ('not a is b', '(is not)',), + ('not a in b', '(not in)',), + ('not a is not b', '(is)',), + ('not a not in b', '(in)',), + ): + asm = dis_single(line) + self.assert_(elem in asm) + + def test_none_as_constant(self): + # LOAD_GLOBAL None --> LOAD_CONST None + def f(x): + None + return x + asm = disassemble(f) + for elem in ('LOAD_GLOBAL',): + self.assert_(elem not in asm) + for elem in ('LOAD_CONST', '(None)'): + self.assert_(elem in asm) + + def test_while_one(self): + # Skip over: LOAD_CONST trueconst JUMP_IF_FALSE xx POP_TOP + def f(): + while 1: + pass + return list + asm = disassemble(f) + for elem in ('LOAD_CONST', 'JUMP_IF_FALSE'): + self.assert_(elem not in asm) + for elem in ('JUMP_ABSOLUTE',): + self.assert_(elem in asm) + + def test_pack_unpack(self): + for line, elem in ( + ('a, = 1,', 'LOAD_CONST',), + ('a, b = 1, 2', 'ROT_TWO',), + ('a, b, c = 1, 2, 3', 'ROT_THREE',), + ): + asm = dis_single(line) + self.assert_(elem in asm) + self.assert_('BUILD_TUPLE' not in asm) + self.assert_('UNPACK_TUPLE' not in asm) + + def test_elim_extra_return(self): + # RETURN LOAD_CONST None RETURN --> RETURN + def f(x): + return x + asm = disassemble(f) + self.assert_('LOAD_CONST' not in asm) + self.assert_('(None)' not in asm) + self.assertEqual(asm.split().count('RETURN_VALUE'), 1) + + + +def test_main(verbose=None): + import sys + from test import test_support + test_classes = (TestTranforms,) + test_support.run_unittest(*test_classes) + + # verify reference counting + if verbose and hasattr(sys, "gettotalrefcount"): + import gc + counts = [None] * 5 + for i in xrange(len(counts)): + test_support.run_unittest(*test_classes) + gc.collect() + counts[i] = sys.gettotalrefcount() + print counts + +if __name__ == "__main__": + test_main(verbose=True) diff --git a/Python/compile.c b/Python/compile.c index 12ab03e..4e7b385 100644 --- a/Python/compile.c +++ b/Python/compile.c @@ -424,11 +424,14 @@ markblocks(unsigned char *code, int len) } static PyObject * -optimize_code(PyObject *code, PyObject* consts, PyObject *names) +optimize_code(PyObject *code, PyObject* consts, PyObject *names, PyObject *lineno_obj) { - int i, j, codelen; + int i, j, codelen, nops, h, adj; int tgt, tgttgt, opcode; - unsigned char *codestr; + unsigned char *codestr = NULL; + unsigned char *lineno; + int *addrmap = NULL; + int new_line, cum_orig_line, last_line, tabsiz; unsigned int *blocks; char *name; @@ -441,23 +444,27 @@ optimize_code(PyObject *code, PyObject* consts, PyObject *names) goto exitUnchanged; codestr = memcpy(codestr, PyString_AS_STRING(code), codelen); + /* Mapping to new jump targets after NOPs are removed */ + addrmap = PyMem_Malloc(codelen * sizeof(int)); + if (addrmap == NULL) + goto exitUnchanged; + /* Avoid situations where jump retargeting could overflow */ - if (codelen > 65000) + if (codelen > 32000) goto exitUnchanged; blocks = markblocks(codestr, codelen); - if (blocks == NULL) { - PyMem_Free(codestr); + if (blocks == NULL) goto exitUnchanged; - } assert(PyTuple_Check(consts)); - for (i=0 ; i a is not b @@ -482,9 +490,10 @@ optimize_code(PyObject *code, PyObject* consts, PyObject *names) if (j < 6 || j > 9 || codestr[i+3] != UNARY_NOT || !ISBASICBLOCK(blocks,i,4)) - continue; + continue; SETARG(codestr, i, (j^1)); codestr[i+3] = NOP; + nops++; break; /* Replace LOAD_GLOBAL/LOAD_NAME None with LOAD_CONST None */ @@ -503,43 +512,40 @@ optimize_code(PyObject *code, PyObject* consts, PyObject *names) } break; - /* Skip over LOAD_CONST trueconst JUMP_IF_FALSE xx POP_TOP. - Note, only the first opcode is changed, the others still - perform normally if they happen to be jump targets. */ + /* Skip over LOAD_CONST trueconst JUMP_IF_FALSE xx POP_TOP */ case LOAD_CONST: j = GETARG(codestr, i); if (codestr[i+3] != JUMP_IF_FALSE || codestr[i+6] != POP_TOP || + !ISBASICBLOCK(blocks,i,7) || !PyObject_IsTrue(PyTuple_GET_ITEM(consts, j))) continue; - codestr[i] = JUMP_FORWARD; - SETARG(codestr, i, 4); + memset(codestr+i, NOP, 7); + nops += 7; break; - /* Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2 JMP+2 NOP NOP. - Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2 JMP+1 NOP. */ + /* Skip over BUILD_SEQN 1 UNPACK_SEQN 1. + Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2. + Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */ case BUILD_TUPLE: case BUILD_LIST: - if (codestr[i+3] != UNPACK_SEQUENCE) - continue; - if (!ISBASICBLOCK(blocks,i,6)) + j = GETARG(codestr, i); + if (codestr[i+3] != UNPACK_SEQUENCE || + !ISBASICBLOCK(blocks,i,6) || + j != GETARG(codestr, i+3)) continue; - if (GETARG(codestr, i) == 2 && - GETARG(codestr, i+3) == 2) { + if (j == 1) { + memset(codestr+i, NOP, 6); + nops += 6; + } else if (j == 2) { codestr[i] = ROT_TWO; - codestr[i+1] = JUMP_FORWARD; - SETARG(codestr, i+1, 2); - codestr[i+4] = NOP; - codestr[i+5] = NOP; - continue; - } - if (GETARG(codestr, i) == 3 && - GETARG(codestr, i+3) == 3) { + memset(codestr+i+1, NOP, 5); + nops += 5; + } else if (j == 3) { codestr[i] = ROT_THREE; codestr[i+1] = ROT_TWO; - codestr[i+2] = JUMP_FORWARD; - SETARG(codestr, i+2, 1); - codestr[i+5] = NOP; + memset(codestr+i+2, NOP, 4); + nops += 4; } break; @@ -570,14 +576,73 @@ optimize_code(PyObject *code, PyObject* consts, PyObject *names) case EXTENDED_ARG: PyMem_Free(codestr); goto exitUnchanged; + + /* Replace RETURN LOAD_CONST None RETURN with just RETURN */ + case RETURN_VALUE: + if (i+4 >= codelen || + codestr[i+4] != RETURN_VALUE || + !ISBASICBLOCK(blocks,i,5)) + continue; + memset(codestr+i+1, NOP, 4); + nops += 4; + break; + } + } + + /* Fixup linenotab */ + assert(PyString_Check(lineno_obj)); + lineno = PyString_AS_STRING(lineno_obj); + tabsiz = PyString_GET_SIZE(lineno_obj); + cum_orig_line = 0; + last_line = 0; + for (i=0 ; i < tabsiz ; i+=2) { + cum_orig_line += lineno[i]; + new_line = addrmap[cum_orig_line]; + lineno[i] =((unsigned char)(new_line - last_line)); + last_line = new_line; + } + + /* Remove NOPs and fixup jump targets */ + for (i=0, h=0 ; i