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.

4 files changed, 206 insertions, 38 deletions

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<codelen ; i += CODESIZE(codestr[i])) {
+	for (i=0, nops=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
+		addrmap[i] = i - nops;
 		opcode = codestr[i];
 		switch (opcode) {
 
 		/* Replace UNARY_NOT JUMP_IF_FALSE POP_TOP with 
-		   with    JUMP_IF_TRUE POP_TOP NOP */
+		   with    JUMP_IF_TRUE POP_TOP */
 		case UNARY_NOT:
 			if (codestr[i+1] != JUMP_IF_FALSE  ||
 			    codestr[i+4] != POP_TOP  ||
@@ -471,6 +478,7 @@ optimize_code(PyObject *code, PyObject* consts, PyObject *names)
 			SETARG(codestr, i, j);
 			codestr[i+3] = POP_TOP;
 			codestr[i+4] = NOP;
+			nops++;
 			break;
 
 		/* not a is b -->  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<codelen ; ) {
+		opcode = codestr[i];
+		switch (opcode) {
+			case NOP:
+				i++;
+				continue;
+
+			case JUMP_ABSOLUTE:
+			case CONTINUE_LOOP:
+				j = addrmap[GETARG(codestr, i)];
+				SETARG(codestr, i, j);
+				break;
+
+			case FOR_ITER:
+			case JUMP_FORWARD:
+			case JUMP_IF_FALSE:
+			case JUMP_IF_TRUE:
+			case SETUP_LOOP:
+			case SETUP_EXCEPT:
+			case SETUP_FINALLY:
+				j = addrmap[GETARG(codestr, i) + i + 3] - addrmap[i] - 3;
+				SETARG(codestr, i, j);
+				break;
 		}
+		adj = CODESIZE(opcode);
+		while (adj--)
+			codestr[h++] = codestr[i++];
 	}
-	code = PyString_FromStringAndSize((char *)codestr, codelen);
+
+	code = PyString_FromStringAndSize((char *)codestr, h);
+	PyMem_Free(addrmap);
 	PyMem_Free(codestr);
 	PyMem_Free(blocks);
 	return code;
 
 exitUnchanged:
+	if (addrmap != NULL)
+		PyMem_Free(addrmap);
+	if (codestr != NULL)
+		PyMem_Free(codestr);
 	Py_INCREF(code);
 	return code;
 }
@@ -4801,7 +4866,7 @@ jcompile(node *n, const char *filename, struct compiling *base,
 					     PyTuple_GET_SIZE(cellvars));
 		filename = PyString_InternFromString(sc.c_filename);
 		name = PyString_InternFromString(sc.c_name);
-		code = optimize_code(sc.c_code, consts, names);
+		code = optimize_code(sc.c_code, consts, names, sc.c_lnotab);
 		if (!PyErr_Occurred())
 			co = PyCode_New(sc.c_argcount,
 					sc.c_nlocals,
diff --git a/Python/import.c b/Python/import.c
index 80427f8..8bbd31b 100644
--- a/Python/import.c
+++ b/Python/import.c
@@ -48,8 +48,9 @@ extern time_t PyOS_GetLastModificationTime(char *, FILE *);
        Python 2.3a0: 62021
        Python 2.3a0: 62011 (!)
        Python 2.4a0: 62041
+       Python 2.4a3: 62051
 */
-#define MAGIC (62041 | ((long)'\r'<<16) | ((long)'\n'<<24))
+#define MAGIC (62051 | ((long)'\r'<<16) | ((long)'\n'<<24))
 
 /* Magic word as global; note that _PyImport_Init() can change the
    value of this global to accommodate for alterations of how the