[Python-checkins] r62457 - in python/branches/tlee-ast-optimize: Include/optimize.h Include/pythonrun.h Lib/test/test_ast.py Lib/test/test_optimizer.py Lib/test/test_peepholer.py Makefile.pre.in Parser/asdl_c.py Python/Python-ast.c Python/ast.c Python/bltinmodule.c Python/compile.c Python/optimize.c Python/peephole.c Python/pythonrun.c

thomas.lee python-checkins at python.org
Tue Apr 22 12:48:18 CEST 2008


Author: thomas.lee
Date: Tue Apr 22 12:48:17 2008
New Revision: 62457

Log:
Applied the patch implementing the AST-level optimizer plus some fixes for a few broken unit tests.

Added:
   python/branches/tlee-ast-optimize/Include/optimize.h
   python/branches/tlee-ast-optimize/Lib/test/test_optimizer.py
   python/branches/tlee-ast-optimize/Python/optimize.c
Modified:
   python/branches/tlee-ast-optimize/Include/pythonrun.h
   python/branches/tlee-ast-optimize/Lib/test/test_ast.py
   python/branches/tlee-ast-optimize/Lib/test/test_peepholer.py
   python/branches/tlee-ast-optimize/Makefile.pre.in
   python/branches/tlee-ast-optimize/Parser/asdl_c.py
   python/branches/tlee-ast-optimize/Python/Python-ast.c
   python/branches/tlee-ast-optimize/Python/ast.c
   python/branches/tlee-ast-optimize/Python/bltinmodule.c
   python/branches/tlee-ast-optimize/Python/compile.c
   python/branches/tlee-ast-optimize/Python/peephole.c
   python/branches/tlee-ast-optimize/Python/pythonrun.c

Added: python/branches/tlee-ast-optimize/Include/optimize.h
==============================================================================
--- (empty file)
+++ python/branches/tlee-ast-optimize/Include/optimize.h	Tue Apr 22 12:48:17 2008
@@ -0,0 +1,15 @@
+#ifndef Py_OPTIMIZE_H
+#define Py_OPTIMIZE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+PyAPI_FUNC(int) PyAST_Optimize(mod_ty* mod_ptr, PyArena* arena);
+
+#ifdef __cplusplus
+};
+#endif
+
+#endif
+

Modified: python/branches/tlee-ast-optimize/Include/pythonrun.h
==============================================================================
--- python/branches/tlee-ast-optimize/Include/pythonrun.h	(original)
+++ python/branches/tlee-ast-optimize/Include/pythonrun.h	Tue Apr 22 12:48:17 2008
@@ -14,6 +14,7 @@
 #define PyCF_SOURCE_IS_UTF8  0x0100
 #define PyCF_DONT_IMPLY_DEDENT 0x0200
 #define PyCF_ONLY_AST 0x0400
+#define PyCF_NO_OPTIMIZE 0x0800
 
 typedef struct {
 	int cf_flags;  /* bitmask of CO_xxx flags relevant to future */

Modified: python/branches/tlee-ast-optimize/Lib/test/test_ast.py
==============================================================================
--- python/branches/tlee-ast-optimize/Lib/test/test_ast.py	(original)
+++ python/branches/tlee-ast-optimize/Lib/test/test_ast.py	Tue Apr 22 12:48:17 2008
@@ -142,7 +142,8 @@
                                     (single_tests, single_results, "single"),
                                     (eval_tests, eval_results, "eval")):
             for i, o in itertools.izip(input, output):
-                ast_tree = compile(i, "?", kind, _ast.PyCF_ONLY_AST)
+                flags = _ast.PyCF_ONLY_AST | _ast.PyCF_NO_OPTIMIZE
+                ast_tree = compile(i, "?", kind, flags)
                 self.assertEquals(to_tuple(ast_tree), o)
                 self._assert_order(ast_tree, (0, 0))
 

Added: python/branches/tlee-ast-optimize/Lib/test/test_optimizer.py
==============================================================================
--- (empty file)
+++ python/branches/tlee-ast-optimize/Lib/test/test_optimizer.py	Tue Apr 22 12:48:17 2008
@@ -0,0 +1,135 @@
+import _ast
+import unittest
+from test import test_support
+
+class AstOptimizerTest(unittest.TestCase):
+    def compileast(self, code):
+        return compile(code, "<string>", "exec", _ast.PyCF_ONLY_AST)
+
+    def test_remove_not_from_if_stmt(self):
+        # ensure we can optimize a boolean "not" out of if statements
+        code = """
+
+x = 10
+
+if not x:
+    1
+else:
+    2
+
+"""
+        ast = self.compileast(code)
+        self.assertEqual(2, len(ast.body))
+        self.assertEqual(_ast.If, ast.body[1].__class__)
+        self.assertEqual(_ast.Name, ast.body[1].test.__class__)
+        self.assertEqual(2, ast.body[1].body[0].value.n)
+        self.assertEqual(1, ast.body[1].orelse[0].value.n)
+
+    def test_fold_if_stmt_with_constants(self):
+        # ensure we can optimize conditionals using simple constants
+        code = """
+if 1:
+    'true'
+else:
+    'false'
+
+if 0:
+    'true'
+else:
+    'false'
+
+"""
+        ast = self.compileast(code)
+        self.assertEqual(2, len(ast.body))
+        self.assertEqual(_ast.Str, ast.body[0].value.__class__)
+        self.assertEqual('true', ast.body[0].value.s)
+        self.assertEqual(_ast.Str, ast.body[1].value.__class__)
+        self.assertEqual('false', ast.body[1].value.s)
+
+    def test_fold_unary_op_before_collapse_branch(self):
+        # ensure unary op folding is applied before collapsing a branch
+        code = """
+if not 1:
+    'true'
+else:
+    'false'
+"""
+        ast = self.compileast(code)
+        self.assertEqual(1, len(ast.body))
+        self.assertEqual(_ast.Str, ast.body[0].value.__class__)
+        self.assertEqual('false', ast.body[0].value.s)
+
+    def assertAstNode(self, expected_type, attr, expected_value, code):
+        ast = self.compileast(code)
+        self.assertEqual(1, len(ast.body))
+        self.assertEqual(expected_type, ast.body[0].value.__class__)
+        if None not in (attr, expected_value):
+            self.assertEqual(expected_value, getattr(ast.body[0].value, attr))
+
+    def assertNum(self, expected, code):
+        return self.assertAstNode(_ast.Num, 'n', expected, code)
+
+    def assertStr(self, expected, code):
+        return self.assertAstNode(_ast.Str, 's', expected, code)
+
+    def test_binop_fold_num(self):
+        # check binary constant folding for numeric values
+        self.assertNum(3, "1 + 2")
+        self.assertNum(18, "2 * 8 + 4 - 2")
+        self.assertNum(16, "2 ** 4")
+        self.assertNum(4, "1 << 2")
+        self.assertAstNode(_ast.BinOp, None, None, "10 / 5")
+
+    def test_binop_fold_num_with_variable(self):
+        # check binary constant folding occurs even where
+        # only partial folding is possible
+
+        # XXX: this will work for x + 3 * 2, but for x + 3 + 2
+        # the constant folding will not occur because the parser builds
+        # something like (+ (+ x 1) 2): need to be more aggressive with these!
+
+        code = """
+x = 5
+x + 3 * 2
+"""
+        ast = self.compileast(code)
+        self.assertEqual(2, len(ast.body))
+        self.assertEqual(_ast.Assign, ast.body[0].__class__)
+        self.assertEqual(_ast.Expr, ast.body[1].__class__)
+        self.assertEqual(_ast.BinOp, ast.body[1].value.__class__)
+        self.assertEqual(_ast.Name, ast.body[1].value.left.__class__)
+        self.assertEqual(_ast.Num, ast.body[1].value.right.__class__)
+        self.assertEqual(6, ast.body[1].value.right.n)
+
+    def test_binop_fold_str(self):
+        # check binary constant folding for string values
+        self.assertStr("hello there", "'hello' + ' ' + 'there'")
+        self.assertStr("testtesttest", "'test' * 3")
+
+    def test_unary_fold_num(self):
+        # check unary constant folding for numeric values
+        self.assertNum(-5, "-5")
+        self.assertNum(True, "not 0")
+        self.assertNum(-3, "-+3")
+        self.assertNum(False, "not True")
+        self.assertNum(True, "not None")
+
+    def test_eliminate_code_after_return(self):
+        # ensure code following a "return" is erased from the AST
+        code = """
+def say_hello():
+    print "Hello there"
+    return True
+    print "A secret message!"
+"""
+        ast = self.compileast(code)
+        self.assertEqual(1, len(ast.body))
+        self.assertEqual(_ast.FunctionDef, ast.body[0].__class__)
+        self.assertEqual(3, len(ast.body[0].body))
+        self.assertEqual(_ast.Pass, ast.body[0].body[2].__class__)
+
+def test_main():
+    test_support.run_unittest(AstOptimizerTest)
+
+if __name__ == '__main__':
+    test_main()

Modified: python/branches/tlee-ast-optimize/Lib/test/test_peepholer.py
==============================================================================
--- python/branches/tlee-ast-optimize/Lib/test/test_peepholer.py	(original)
+++ python/branches/tlee-ast-optimize/Lib/test/test_peepholer.py	Tue Apr 22 12:48:17 2008
@@ -107,56 +107,6 @@
                 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
             ],)
 
-    def test_folding_of_binops_on_constants(self):
-        for line, elem in (
-            ('a = 2+3+4', '(9)'),                   # chained fold
-            ('"@"*4', "('@@@@')"),                  # check string ops
-            ('a="abc" + "def"', "('abcdef')"),      # check string ops
-            ('a = 3**4', '(81)'),                   # binary power
-            ('a = 3*4', '(12)'),                    # binary multiply
-            ('a = 13//4', '(3)'),                   # binary floor divide
-            ('a = 14%4', '(2)'),                    # binary modulo
-            ('a = 2+3', '(5)'),                     # binary add
-            ('a = 13-4', '(9)'),                    # binary subtract
-            ('a = (12,13)[1]', '(13)'),             # binary subscr
-            ('a = 13 << 2', '(52)'),                # binary lshift
-            ('a = 13 >> 2', '(3)'),                 # binary rshift
-            ('a = 13 & 7', '(5)'),                  # binary and
-            ('a = 13 ^ 7', '(10)'),                 # binary xor
-            ('a = 13 | 7', '(15)'),                 # binary or
-            ):
-            asm = dis_single(line)
-            self.assert_(elem in asm, asm)
-            self.assert_('BINARY_' not in asm)
-
-        # Verify that unfoldables are skipped
-        asm = dis_single('a=2+"b"')
-        self.assert_('(2)' in asm)
-        self.assert_("('b')" in asm)
-
-        # Verify that large sequences do not result from folding
-        asm = dis_single('a="x"*1000')
-        self.assert_('(1000)' in asm)
-
-    def test_folding_of_unaryops_on_constants(self):
-        for line, elem in (
-            ('`1`', "('1')"),                       # unary convert
-            ('-0.5', '(-0.5)'),                     # unary negative
-            ('~-2', '(1)'),                         # unary invert
-        ):
-            asm = dis_single(line)
-            self.assert_(elem in asm, asm)
-            self.assert_('UNARY_' not in asm)
-
-        # Verify that unfoldables are skipped
-        for line, elem in (
-            ('-"abc"', "('abc')"),                  # unary negative
-            ('~"abc"', "('abc')"),                  # unary invert
-        ):
-            asm = dis_single(line)
-            self.assert_(elem in asm, asm)
-            self.assert_('UNARY_' in asm)
-
     def test_elim_extra_return(self):
         # RETURN LOAD_CONST None RETURN  -->  RETURN
         def f(x):
@@ -175,34 +125,6 @@
         self.assert_('JUMP_ABSOLUTE' not in asm)
         self.assertEqual(asm.split().count('RETURN_VALUE'), 2)
 
-    def test_elim_jump_after_return1(self):
-        # Eliminate dead code: jumps immediately after returns can't be reached
-        def f(cond1, cond2):
-            if cond1: return 1
-            if cond2: return 2
-            while 1:
-                return 3
-            while 1:
-                if cond1: return 4
-                return 5
-            return 6
-        asm = disassemble(f)
-        self.assert_('JUMP_FORWARD' not in asm)
-        self.assert_('JUMP_ABSOLUTE' not in asm)
-        self.assertEqual(asm.split().count('RETURN_VALUE'), 6)
-
-    def test_elim_jump_after_return2(self):
-        # Eliminate dead code: jumps immediately after returns can't be reached
-        def f(cond1, cond2):
-            while 1:
-                if cond1: return 4
-        asm = disassemble(f)
-        self.assert_('JUMP_FORWARD' not in asm)
-        # There should be one jump for the while loop.
-        self.assertEqual(asm.split().count('JUMP_ABSOLUTE'), 1)
-        self.assertEqual(asm.split().count('RETURN_VALUE'), 2)
-
-
 def test_main(verbose=None):
     import sys
     from test import test_support

Modified: python/branches/tlee-ast-optimize/Makefile.pre.in
==============================================================================
--- python/branches/tlee-ast-optimize/Makefile.pre.in	(original)
+++ python/branches/tlee-ast-optimize/Makefile.pre.in	Tue Apr 22 12:48:17 2008
@@ -253,6 +253,7 @@
 		Python/Python-ast.o \
 		Python/asdl.o \
 		Python/ast.o \
+		Python/optimize.o \
 		Python/bltinmodule.o \
 		Python/ceval.o \
 		Python/compile.o \

Modified: python/branches/tlee-ast-optimize/Parser/asdl_c.py
==============================================================================
--- python/branches/tlee-ast-optimize/Parser/asdl_c.py	(original)
+++ python/branches/tlee-ast-optimize/Parser/asdl_c.py	Tue Apr 22 12:48:17 2008
@@ -889,6 +889,8 @@
         self.emit('if (PyDict_SetItemString(d, "AST", (PyObject*)&AST_type) < 0) return;', 1)
         self.emit('if (PyModule_AddIntConstant(m, "PyCF_ONLY_AST", PyCF_ONLY_AST) < 0)', 1)
         self.emit("return;", 2)
+        self.emit('if (PyModule_AddIntConstant(m, "PyCF_NO_OPTIMIZE", PyCF_NO_OPTIMIZE) < 0)', 1)
+        self.emit("return;", 2)
         # Value of version: "$Revision$"
         self.emit('if (PyModule_AddStringConstant(m, "__version__", "%s") < 0)'
                 % parse_version(mod), 1)

Modified: python/branches/tlee-ast-optimize/Python/Python-ast.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/Python-ast.c	(original)
+++ python/branches/tlee-ast-optimize/Python/Python-ast.c	Tue Apr 22 12:48:17 2008
@@ -5932,6 +5932,9 @@
         if (PyDict_SetItemString(d, "AST", (PyObject*)&AST_type) < 0) return;
         if (PyModule_AddIntConstant(m, "PyCF_ONLY_AST", PyCF_ONLY_AST) < 0)
                 return;
+        if (PyModule_AddIntConstant(m, "PyCF_NO_OPTIMIZE", PyCF_NO_OPTIMIZE) <
+            0)
+                return;
         if (PyModule_AddStringConstant(m, "__version__", "62047") < 0)
                 return;
         if (PyDict_SetItemString(d, "mod", (PyObject*)mod_type) < 0) return;

Modified: python/branches/tlee-ast-optimize/Python/ast.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/ast.c	(original)
+++ python/branches/tlee-ast-optimize/Python/ast.c	Tue Apr 22 12:48:17 2008
@@ -3366,3 +3366,4 @@
         Py_XDECREF(v);
         return NULL;
 }
+

Modified: python/branches/tlee-ast-optimize/Python/bltinmodule.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/bltinmodule.c	(original)
+++ python/branches/tlee-ast-optimize/Python/bltinmodule.c	Tue Apr 22 12:48:17 2008
@@ -6,6 +6,7 @@
 #include "node.h"
 #include "code.h"
 #include "eval.h"
+#include "optimize.h"
 
 #include <ctype.h>
 
@@ -472,6 +473,11 @@
 	PyCompilerFlags cf;
 	PyObject *result = NULL, *cmd, *tmp = NULL;
 	Py_ssize_t length;
+    static const int allowed_flags = PyCF_MASK |
+                                        PyCF_MASK_OBSOLETE |
+                                        PyCF_DONT_IMPLY_DEDENT |
+                                        PyCF_ONLY_AST |
+                                        PyCF_NO_OPTIMIZE;
 	static char *kwlist[] = {"source", "filename", "mode", "flags",
 				 "dont_inherit", NULL};
 	int start[] = {Py_file_input, Py_eval_input, Py_single_input};
@@ -483,8 +489,7 @@
 
 	cf.cf_flags = supplied_flags;
 
-	if (supplied_flags &
-	    ~(PyCF_MASK | PyCF_MASK_OBSOLETE | PyCF_DONT_IMPLY_DEDENT | PyCF_ONLY_AST))
+	if (supplied_flags & ~allowed_flags)
 	{
 		PyErr_SetString(PyExc_ValueError,
 				"compile(): unrecognised flags");
@@ -523,8 +528,13 @@
 				PyArena_Free(arena);
 				return NULL;
 			}
-			result = (PyObject*)PyAST_Compile(mod, filename,
-							  &cf, arena);
+            if (!(supplied_flags & PyCF_NO_OPTIMIZE)) {
+                if (!PyAST_Optimize(&mod, arena)) {
+                    PyArena_Free(arena);
+                    return NULL;
+                }
+            }
+			result = (PyObject*)PyAST_Compile(mod, filename, &cf, arena);
 			PyArena_Free(arena);
 		}
 		return result;

Modified: python/branches/tlee-ast-optimize/Python/compile.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/compile.c	(original)
+++ python/branches/tlee-ast-optimize/Python/compile.c	Tue Apr 22 12:48:17 2008
@@ -31,6 +31,7 @@
 #include "compile.h"
 #include "symtable.h"
 #include "opcode.h"
+#include "optimize.h"
 
 int Py_OptimizeFlag = 0;
 
@@ -298,8 +299,11 @@
 	if (!arena)
 		return NULL;
 	mod = PyAST_FromNode(n, NULL, filename, arena);
-	if (mod)
-		co = PyAST_Compile(mod, filename, NULL, arena);
+	if (mod != NULL) {
+        if (PyAST_Optimize(&mod, arena)) {
+            co = PyAST_Compile(mod, filename, NULL, arena);
+        }
+    }
 	PyArena_Free(arena);
 	return co;
 }

Added: python/branches/tlee-ast-optimize/Python/optimize.c
==============================================================================
--- (empty file)
+++ python/branches/tlee-ast-optimize/Python/optimize.c	Tue Apr 22 12:48:17 2008
@@ -0,0 +1,1204 @@
+#include "Python.h"
+#include "Python-ast.h"
+#include "pyarena.h"
+#include "pyerrors.h"
+#include "node.h"
+#include "ast.h"
+
+static int optimize_expr(expr_ty* expr_ptr, PyArena* arena);
+static int optimize_stmt(stmt_ty* stmt_ptr, PyArena* arena);
+static int optimize_comprehension(comprehension_ty* comp_ptr, PyArena* arena);
+static int optimize_excepthandler(excepthandler_ty* exc_ptr, PyArena* arena);
+static int optimize_keyword(keyword_ty* kwd_ptr, PyArena* arena);
+static int optimize_arguments(arguments_ty* args_ptr, PyArena* arena);
+static int optimize_slice(slice_ty* slice_ptr, PyArena* arena);
+
+/**
+ * Determine the constant value of a given expression. It's assumed that
+ * constants have been folded.
+ */
+static PyObject*
+_expr_constant_value(expr_ty expr)
+{
+    if (expr->kind == Str_kind) {
+        return expr->v.Str.s;
+    }
+    else if (expr->kind == Num_kind) {
+        return expr->v.Num.n;
+    }
+    else if (expr->kind == Name_kind) {
+        const char* name = PyString_AS_STRING(expr->v.Name.id);
+        if (strcmp(name, "True") == 0)
+            return Py_True;
+        else if (strcmp(name, "False") == 0)
+            return Py_False;
+        else if (strcmp(name, "None") == 0)
+            return Py_None;
+    }
+    return NULL;
+}
+
+/**
+ * Determine whether or not the given expression represents a constant value.
+ * This makes the assumption that constants have already been folded.
+ */
+static int
+_expr_is_constant(expr_ty expr)
+{
+    return _expr_constant_value(expr) != NULL;
+}
+
+/*
+ * builds a Name() node with a Load context from the given id.
+ */
+static expr_ty
+_make_name(PyObject* id, int lineno, int col_offset, PyArena* arena)
+{
+    expr_ty expr;
+    if (id == NULL)
+        return NULL;
+    expr = Name(id, Load, lineno, col_offset, arena);
+    if (expr == NULL)
+        return NULL;
+    return expr;
+}
+
+/**
+ * Builds an expr from the given constant value. Constant values can be
+ * any Str or Num, or any one of True/False/None.
+ */
+static expr_ty
+_expr_from_object(PyObject* object, int lineno, int col_offset, PyArena* arena)
+{
+    expr_ty expr = NULL;
+
+    if (PyString_Check(object) || PyUnicode_Check(object)) {
+        Py_INCREF(object);
+        expr = Str(object, lineno, col_offset, arena);
+    }
+    else if (PyNumber_Check(object)) {
+        Py_INCREF(object);
+        expr = Num(object, lineno, col_offset, arena);
+    }
+    else if (object == Py_None) {
+        object = PyString_FromString("None");
+        expr = _make_name(object, lineno, col_offset, arena);
+    }
+    else if (object == Py_True) {
+        object = PyString_FromString("True");
+        expr = _make_name(object, lineno, col_offset, arena);
+    }
+    else if (object == Py_False) {
+        object = PyString_FromString("False");
+        expr = _make_name(object, lineno, col_offset, arena);
+    }
+    else {
+        PyErr_Format(PyExc_TypeError, "unknown constant value");
+        return NULL;
+    }
+
+    if (expr == NULL)
+        return NULL;
+
+    if (PyArena_AddPyObject(arena, object) == -1) {
+        /* exception will be set in PyArena_AddPyObject */
+        Py_DECREF(object);
+        return NULL;
+    }
+
+    /* PyArena_AddPyObject decrements the refcount for us */
+    return expr;
+}
+
+/**
+ * Returns 1 if the given expression evaluates to a true value. Otherwise,
+ * returns 0. This function assumes that the given expr is constant.
+ */
+static int
+_expr_is_true(expr_ty expr)
+{
+    assert(_expr_is_constant(expr));
+    return PyObject_IsTrue(_expr_constant_value(expr));
+}
+
+/**
+ * Optimize a sequence of expressions.
+ */
+static int
+optimize_expr_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++)
+        if (!optimize_expr((expr_ty*)&asdl_seq_GET(seq, n), arena))
+            return 0;
+    return 1;
+}
+
+#if 0
+/**
+ * Shrink an ASDL sequence by trimming off the last few elements.
+ */
+static asdl_seq*
+_asdl_seq_shrink(asdl_seq* seq, int newlen, PyArena* arena)
+{
+    asdl_seq* new;
+    int n;
+    new = asdl_seq_new(newlen, arena);
+    if (new == NULL)
+        return NULL;
+    for (n = 0; n < newlen; n++)
+        asdl_seq_SET(new, n, asdl_seq_GET(seq, n));
+    return new;
+}
+#endif
+
+/**
+ * Replace an AST node at position `n' with the node(s) in `replacement'.
+ */
+static asdl_seq*
+_asdl_seq_replace(asdl_seq* seq, int n, asdl_seq* replacement, PyArena* arena)
+{
+    asdl_seq* new;
+    int newlen, replen, i;
+
+    assert(replacement != NULL);
+    /* at the very least, we should have a single node */
+    assert(asdl_seq_LEN(replacement) > 0);
+
+    newlen = asdl_seq_LEN(seq) - 1;
+    replen = asdl_seq_LEN(replacement);
+    newlen += replen;
+
+    assert(newlen > 0);
+
+    new = asdl_seq_new(newlen, arena);
+    if (new == NULL)
+        return NULL;
+
+    /* copy everything before position `n` into the new seq */
+    for (i = 0; i < n; i++)
+        asdl_seq_SET(new, i, asdl_seq_GET(seq, i));
+
+    /* if we have a replacement, append it to the new seq */
+    if (replacement != NULL)
+        for (i = n; i < n + replen; i++)
+            asdl_seq_SET(new, i, asdl_seq_GET(replacement, i - n));
+
+    /* append everything after position `n` to the new seq */
+    for (i = n + replen; i < newlen; i++)
+        asdl_seq_SET(new, i, asdl_seq_GET(seq, (i - replen) + 1));
+
+    return new;
+}
+
+/**
+ * Replaces the AST node at `n' with a Pass() node.
+ */
+static asdl_seq*
+_asdl_seq_replace_with_pass(asdl_seq* seq, int n, int lineno, int col_offset, PyArena* arena)
+{
+    stmt_ty pass;
+    asdl_seq* new;
+
+    pass = Pass(lineno, col_offset, arena);
+    if (pass == NULL)
+        return NULL;
+    new = asdl_seq_new(1, arena);
+    if (new == NULL)
+        return NULL;
+    asdl_seq_SET(new, 0, pass);
+    
+    return _asdl_seq_replace(seq, n, new, arena);
+}
+
+/**
+ * Optimize a sequence of statements.
+ */
+static int
+optimize_stmt_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++) {
+        stmt_ty stmt = asdl_seq_GET(seq, n);
+        if (!optimize_stmt((stmt_ty*)&asdl_seq_GET(seq, n), arena))
+            return 0;
+
+        if (stmt->kind == If_kind) {
+            /* eliminate branches that can never be reached */
+            if (_expr_is_constant(stmt->v.If.test)) {
+                if (_expr_is_true(stmt->v.If.test))
+                    seq = _asdl_seq_replace(seq, n, stmt->v.If.body, arena);
+                else {
+                    if (stmt->v.If.orelse == NULL) {
+                        /* no "else:" body: use a Pass() */
+                        seq = _asdl_seq_replace_with_pass(seq, n,
+                                stmt->lineno, stmt->col_offset, arena);
+                    }
+                    else {
+                        seq = _asdl_seq_replace(seq, n, stmt->v.If.orelse,
+                                arena);
+                    }
+                }
+                if (seq == NULL)
+                    return 0;
+                *seq_ptr = seq;
+            }
+        }
+        else if (stmt->kind == Return_kind) {
+            /* eliminate all nodes after a return */
+            seq = _asdl_seq_replace_with_pass(seq, n + 1,
+                    stmt->lineno, stmt->col_offset, arena);
+            if (seq == NULL)
+                return 0;
+            *seq_ptr = seq;
+        }
+    }
+    return 1;
+}
+
+static int
+optimize_comprehension_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++) {
+        comprehension_ty* comp;
+        comp = (comprehension_ty*)&asdl_seq_GET(seq, n);
+        if (!optimize_comprehension(comp, arena))
+            return 0;
+    }
+    return 1;
+}
+
+static int
+optimize_excepthandler_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++) {
+        excepthandler_ty* excepthandler;
+        excepthandler = (excepthandler_ty*)&asdl_seq_GET(seq, n);
+        if (!optimize_excepthandler(excepthandler, arena))
+            return 0;
+    }
+    return 1;
+}
+
+static int
+optimize_keyword_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++)
+        if (!optimize_keyword((keyword_ty*)&asdl_seq_GET(seq, n), arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_slice_seq(asdl_seq** seq_ptr, PyArena* arena)
+{
+    int n;
+    asdl_seq* seq = *seq_ptr;
+    for (n = 0; n < asdl_seq_LEN(seq); n++)
+        if (!optimize_slice((slice_ty*)&asdl_seq_GET(seq, n), arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_mod(mod_ty* mod_ptr, PyArena* arena)
+{
+    asdl_seq** body;
+    mod_ty mod = *mod_ptr;
+
+    switch (mod->kind) {
+        case Module_kind:
+            {
+                body = &mod->v.Module.body;
+                break;
+            }
+        case Interactive_kind:
+            {
+                body = &mod->v.Interactive.body;
+                break;
+            }
+        case Suite_kind:
+            {
+                body = &mod->v.Suite.body;
+                break;
+            }
+        case Expression_kind:
+            {
+                return optimize_expr(&mod->v.Expression.body, arena);
+            }
+        default:
+            PyErr_Format(PyExc_ValueError, "unknown mod_ty kind: %d",
+                    mod->kind);
+            return 0;
+    };
+
+    return optimize_stmt_seq(body, arena);
+}
+
+static int
+optimize_bool_op(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr_seq(&expr->v.BoolOp.values, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_bin_op(expr_ty* expr_ptr, PyArena* arena)
+{
+    PyObject* left;
+    PyObject* right;
+    expr_ty expr = *expr_ptr;
+
+    if (!optimize_expr(&expr->v.BinOp.left, arena))
+        return 0;
+    if (!optimize_expr(&expr->v.BinOp.right, arena))
+        return 0;
+
+    /* 
+     * TODO: aggressively rearrange binop grouping so that as many constants
+     * as possible are grouped together
+     */
+
+    left = _expr_constant_value(expr->v.BinOp.left);
+    right = _expr_constant_value(expr->v.BinOp.right);
+
+    /* if the left & right hand side are constant values, we can fold them */
+    if (left != NULL && right != NULL) {
+        PyObject* res = NULL;
+        int size;
+
+        switch (expr->v.BinOp.op) {
+            case Add:
+                {
+                    res = PyNumber_Add(left, right);
+                    break;
+                }
+            case Sub:
+                {
+                    res = PyNumber_Subtract(left, right);
+                    break;
+                }
+            case Mult:
+                {
+                    res = PyNumber_Multiply(left, right);
+                    break;
+                }
+            case Div:
+                {
+                    /* XXX: -Qnew will break this. Fixes test_binop ... */
+                    /* TODO: this should be okay in Python-3000 */
+#if 0
+                    /* avoid divide-by-zero errors */
+                    if (PyObject_IsTrue(right))
+                        res = PyNumber_TrueDivide(left, right);
+#endif
+                    break;
+                }
+            case Mod:
+                {
+                    /* avoid divide-by-zero errors */
+                    if (PyObject_IsTrue(right))
+                        res = PyNumber_Remainder(left, right);
+                    break;
+                }
+            case Pow:
+                {
+                    res = PyNumber_Power(left, right, Py_None);
+                    break;
+                }
+            case LShift:
+                {
+                    res = PyNumber_Lshift(left, right);
+                    break;
+                }
+            case RShift:
+                {
+                    res = PyNumber_Rshift(left, right);
+                    break;
+                }
+            case BitOr:
+                {
+                    res = PyNumber_Or(left, right);
+                    break;
+                }
+            case BitXor:
+                {
+                    res = PyNumber_Xor(left, right);
+                    break;
+                }
+            case BitAnd:
+                {
+                    res = PyNumber_And(left, right);
+                    break;
+                }
+            case FloorDiv:
+                {
+                    /* avoid divide-by-zero errors */
+                    if (PyObject_IsTrue(right))
+                        res = PyNumber_FloorDivide(left, right);
+                    break;
+                }
+            default:
+                PyErr_Format(PyExc_ValueError, "unknown binary operator: %d",
+                        expr->v.BinOp.op);
+                return 0;
+        }
+        
+        if (res == NULL) {
+            if (PyErr_Occurred()) {
+                /* if we're out of memory, we need to complain about it now! */
+                if (PyErr_ExceptionMatches(PyExc_MemoryError)) {
+                    return 0;
+                }
+                /* otherwise, the binop failed: clear the error */
+                else
+                    PyErr_Clear();
+            }
+            /* do not optimize this expression */
+            return 1;
+        }
+
+        size = PyObject_Size(res);
+        if (size == -1) {
+            PyErr_Clear();
+        }
+        else if (size >= 20) {
+            Py_DECREF(res);
+            return 1;
+        }
+        
+        expr = _expr_from_object(res, expr->lineno, expr->col_offset, arena);
+        if (expr == NULL) {
+            Py_DECREF(res);
+            return 0;
+        }
+        *expr_ptr = expr;
+
+        Py_DECREF(res);
+    }
+
+    return 1;
+}
+
+static int
+optimize_unary_op(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.UnaryOp.operand, arena))
+        return 0;
+    if (_expr_is_constant(expr->v.UnaryOp.operand)) {
+        PyObject* operand;
+        PyObject* res;
+
+        operand = _expr_constant_value(expr->v.UnaryOp.operand);
+        if (operand == NULL) {
+            /* XXX this should never happen ... */
+            PyErr_Format(PyExc_ValueError, "unknown constant type: %d",
+                    expr->v.UnaryOp.operand->kind);
+            return 0;
+        }
+
+        switch (expr->v.UnaryOp.op) {
+            case Invert:
+                {
+                    res = PyNumber_Invert(operand);
+                    break;
+                }
+            case Not:
+                {
+                    res = PyBool_FromLong(PyObject_Not(operand));
+                    break;
+                }
+            case UAdd:
+                {
+                    res = PyNumber_Positive(operand);
+                    break;
+                }
+            case USub:
+                {
+                    /* ensure -0.0/+0.0 are not touched */
+                    if (PyObject_IsTrue(operand))
+                        res = PyNumber_Negative(operand);
+                    else
+                        return 1;
+
+                    break;
+                }
+            default:
+                PyErr_Format(PyExc_ValueError, "unknown unary op: %d",
+                        expr->v.UnaryOp.op);
+                return 0;
+        }
+
+        if (res == NULL)
+            return 0;
+
+        expr = _expr_from_object(res, expr->lineno, expr->col_offset, arena);
+        if (!expr) {
+            Py_DECREF(res);
+            return 0;
+        }
+        *expr_ptr = expr;
+
+        Py_DECREF(res);
+    }
+    return 1;
+}
+
+static int
+optimize_lambda(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Lambda.body, arena))
+        return 0;
+    return 1;
+}
+
+static int optimize_if_exp(expr_ty* expr_ptr, PyArena* arena) {
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.IfExp.test, arena))
+        return 0;
+    if (!optimize_expr(&expr->v.IfExp.body, arena))
+        return 0;
+    if (!optimize_expr(&expr->v.IfExp.orelse, arena))
+        return 0;
+    return 1;
+}
+
+static int optimize_dict(expr_ty* expr_ptr, PyArena* arena) {
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr_seq(&expr->v.Dict.keys, arena))
+        return 0;
+    if (!optimize_expr_seq(&expr->v.Dict.values, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_comprehension(comprehension_ty* comp_ptr, PyArena* arena)
+{
+    comprehension_ty comp = *comp_ptr;
+    if (!optimize_expr(&comp->target, arena))
+        return 0;
+    if (!optimize_expr(&comp->iter, arena))
+        return 0;
+    if (!optimize_expr_seq(&comp->ifs, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_list_comp(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.ListComp.elt, arena))
+        return 0;
+    if (!optimize_comprehension_seq(&expr->v.ListComp.generators, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_generator_exp(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.GeneratorExp.elt, arena))
+        return 0;
+    if (!optimize_comprehension_seq(&expr->v.GeneratorExp.generators, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_yield(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (expr->v.Yield.value != NULL)
+        if (!optimize_expr(&expr->v.Yield.value, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_compare(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Compare.left, arena))
+        return 0;
+    if (!optimize_expr_seq(&expr->v.Compare.comparators, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_keyword(keyword_ty* keyword_ptr, PyArena* arena)
+{
+    keyword_ty keyword = *keyword_ptr;
+    if (!optimize_expr(&keyword->value, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_arguments(arguments_ty* args_ptr, PyArena* arena)
+{
+    arguments_ty args = *args_ptr;
+    if (!optimize_expr_seq(&args->args, arena))
+        return 0;
+    if (!optimize_expr_seq(&args->defaults, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_call(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Call.func, arena))
+        return 0;
+    if (!optimize_expr_seq(&expr->v.Call.args, arena))
+        return 0;
+    if (!optimize_keyword_seq(&expr->v.Call.keywords, arena))
+        return 0;
+    if (expr->v.Call.starargs != NULL)
+        if (!optimize_expr(&expr->v.Call.starargs, arena))
+            return 0;
+    if (expr->v.Call.kwargs != NULL)
+        if (!optimize_expr(&expr->v.Call.kwargs, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_repr(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Repr.value, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_attribute(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Attribute.value, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_slice(slice_ty* slice_ptr, PyArena* arena)
+{
+    slice_ty slice = *slice_ptr;
+    switch (slice->kind) {
+        case Slice_kind:
+            {
+                if (slice->v.Slice.lower != NULL)
+                    if (!optimize_expr(&slice->v.Slice.lower, arena))
+                        return 0;
+                if (slice->v.Slice.upper != NULL)
+                    if (!optimize_expr(&slice->v.Slice.upper, arena))
+                        return 0;
+                if (slice->v.Slice.step != NULL)
+                    if (!optimize_expr(&slice->v.Slice.step, arena))
+                        return 0;
+                break;
+            }
+        case ExtSlice_kind:
+            {
+                if (!optimize_slice_seq(&slice->v.ExtSlice.dims, arena))
+                    return 0;
+                break;
+            }
+        case Index_kind:
+            {
+                if (!optimize_expr(&slice->v.Index.value, arena))
+                    return 0;
+                break;
+            }
+        case Ellipsis_kind:
+            {
+                return 1;
+            }
+        default:
+            PyErr_Format(PyExc_ValueError, "unknown slice kind: %d",
+                    slice->kind);
+            return 0;
+    }
+    return 1;
+}
+
+static int
+optimize_subscript(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    if (!optimize_expr(&expr->v.Subscript.value, arena))
+        return 0;
+    if (!optimize_slice(&expr->v.Subscript.slice, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_expr(expr_ty* expr_ptr, PyArena* arena)
+{
+    expr_ty expr = *expr_ptr;
+    switch (expr->kind) {
+        case BoolOp_kind:
+            {
+                return optimize_bool_op(expr_ptr, arena);
+            }
+        case BinOp_kind:
+            {
+                return optimize_bin_op(expr_ptr, arena);
+            }
+        case UnaryOp_kind:
+            {
+                return optimize_unary_op(expr_ptr, arena);
+            }
+        case Lambda_kind:
+            {
+                return optimize_lambda(expr_ptr, arena);
+            }
+        case IfExp_kind:
+            {
+                return optimize_if_exp(expr_ptr, arena);
+            }
+        case Dict_kind:
+            {
+                return optimize_dict(expr_ptr, arena);
+            }
+        case ListComp_kind:
+            {
+                return optimize_list_comp(expr_ptr, arena);
+            }
+        case GeneratorExp_kind:
+            {
+                return optimize_generator_exp(expr_ptr, arena);
+            }
+        case Yield_kind:
+            {
+                return optimize_yield(expr_ptr, arena);
+            }
+        case Compare_kind:
+            {
+                return optimize_compare(expr_ptr, arena);
+            }
+        case Call_kind:
+            {
+                return optimize_call(expr_ptr, arena);
+            }
+        case Repr_kind:
+            {
+                return optimize_repr(expr_ptr, arena);
+            }
+        case Attribute_kind:
+            {
+                return optimize_attribute(expr_ptr, arena);
+            }
+        case Subscript_kind:
+            {
+                return optimize_subscript(expr_ptr, arena);
+            }
+        case List_kind:
+            {
+                return optimize_expr_seq(&expr->v.List.elts, arena);
+            }
+        case Tuple_kind:
+            {
+                return optimize_expr_seq(&expr->v.Tuple.elts, arena);
+            }
+        case Num_kind:
+        case Str_kind:
+        case Name_kind:
+            {
+                return 1;
+            }
+        default:
+            PyErr_Format(PyExc_ValueError, "unknown expr_ty kind: %d",
+                    expr->kind);
+            return 0;
+    }
+}
+
+static int
+optimize_function_def(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_arguments(&stmt->v.FunctionDef.args, arena))
+        return 0;
+    if (!optimize_expr_seq(&stmt->v.FunctionDef.decorator_list, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.FunctionDef.body, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_class_def(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr_seq(&stmt->v.ClassDef.bases, arena))
+        return 0;
+    if (!optimize_expr_seq(&stmt->v.ClassDef.decorator_list, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.ClassDef.body, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_return(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (stmt->v.Return.value != NULL)
+        if (!optimize_expr(&stmt->v.Return.value, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_delete(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr_seq(&stmt->v.Delete.targets, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_assign(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr_seq(&stmt->v.Assign.targets, arena))
+        return 0;
+    if (!optimize_expr(&stmt->v.Assign.value, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_aug_assign(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.AugAssign.target, arena))
+        return 0;
+    if (!optimize_expr(&stmt->v.AugAssign.value, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_print(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+
+    if (stmt->v.Print.dest != NULL)
+        if (!optimize_expr(&stmt->v.Print.dest, arena))
+            return 0;
+    if (!optimize_expr_seq(&stmt->v.Print.values, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_for(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.For.target, arena))
+        return 0;
+    if (!optimize_expr(&stmt->v.For.iter, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.For.body, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.For.orelse, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_while(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.While.test, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.While.body, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.While.orelse, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_if(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+
+    if (!optimize_expr(&stmt->v.If.test, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.If.body, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.If.orelse, arena))
+        return 0;
+
+    if (stmt->v.If.test->kind == UnaryOp_kind &&
+            stmt->v.If.test->v.UnaryOp.op == Not) {
+        asdl_seq* body = stmt->v.If.orelse;
+        if (body == NULL) {
+            /* body can't be NULL, so let's turn this into a Pass() */
+            stmt_ty pass = Pass(stmt->lineno, stmt->col_offset, arena);
+            if (pass == NULL)
+                return 0;
+
+            body = asdl_seq_new(1, arena);
+            if (body == NULL)
+                return 0;
+
+            asdl_seq_SET(body, 0, pass);
+        }
+        *stmt_ptr = If(stmt->v.If.test->v.UnaryOp.operand,
+                        body,
+                        stmt->v.If.body,
+                        stmt->lineno, stmt->col_offset, arena);
+        if (*stmt_ptr == NULL)
+            return 0;
+    }
+
+    return 1;
+}
+
+static int
+optimize_with(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.With.context_expr, arena))
+        return 0;
+    if (stmt->v.With.optional_vars != NULL)
+        if (!optimize_expr(&stmt->v.With.optional_vars, arena))
+            return 0;
+    if (!optimize_stmt_seq(&stmt->v.With.body, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_raise(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (stmt->v.Raise.type != NULL)
+        if (!optimize_expr(&stmt->v.Raise.type, arena))
+            return 0;
+    if (stmt->v.Raise.inst != NULL)
+        if (!optimize_expr(&stmt->v.Raise.inst, arena))
+            return 0;
+    if (stmt->v.Raise.tback != NULL)
+        if (!optimize_expr(&stmt->v.Raise.tback, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_excepthandler(excepthandler_ty* exc_ptr, PyArena* arena)
+{
+    excepthandler_ty exc = *exc_ptr;
+    if (exc->v.ExceptHandler.type != NULL)
+        if (!optimize_expr(&exc->v.ExceptHandler.type, arena))
+            return 0;
+    if (exc->v.ExceptHandler.name != NULL)
+        if (!optimize_expr(&exc->v.ExceptHandler.name, arena))
+            return 0;
+    if (!optimize_stmt_seq(&exc->v.ExceptHandler.body, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_try_except(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_stmt_seq(&stmt->v.TryExcept.body, arena))
+        return 0;
+    if (!optimize_excepthandler_seq(&stmt->v.TryExcept.handlers, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.TryExcept.orelse, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_try_finally(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_stmt_seq(&stmt->v.TryFinally.body, arena))
+        return 0;
+    if (!optimize_stmt_seq(&stmt->v.TryFinally.finalbody, arena))
+        return 0;
+    return 1;
+}
+
+static int
+optimize_assert(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.Assert.test, arena))
+        return 0;
+    if (stmt->v.Assert.msg != NULL)
+        if (!optimize_expr(&stmt->v.Assert.msg, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_import(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    return 1;
+}
+
+static int
+optimize_import_from(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    return 1;
+}
+
+static int
+optimize_exec(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+    if (!optimize_expr(&stmt->v.Exec.body, arena))
+        return 0;
+    if (stmt->v.Exec.globals != NULL)
+        if (!optimize_expr(&stmt->v.Exec.globals, arena))
+            return 0;
+    if (stmt->v.Exec.locals != NULL)
+        if (!optimize_expr(&stmt->v.Exec.locals, arena))
+            return 0;
+    return 1;
+}
+
+static int
+optimize_global(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    return 1;
+}
+
+static int
+optimize_stmt(stmt_ty* stmt_ptr, PyArena* arena)
+{
+    stmt_ty stmt = *stmt_ptr;
+
+    switch (stmt->kind) {
+        case FunctionDef_kind:
+            {
+                return optimize_function_def(stmt_ptr, arena);
+            }
+        case ClassDef_kind:
+            {
+                return optimize_class_def(stmt_ptr, arena);
+            }
+        case Return_kind:
+            {
+                return optimize_return(stmt_ptr, arena);
+            }
+        case Delete_kind:
+            {
+                return optimize_delete(stmt_ptr, arena);
+            }
+        case Assign_kind:
+            {
+                return optimize_assign(stmt_ptr, arena);
+            }
+        case AugAssign_kind:
+            {
+                return optimize_aug_assign(stmt_ptr, arena);
+            }
+        case Print_kind:
+            {
+                return optimize_print(stmt_ptr, arena);
+            }
+        case For_kind:
+            {
+                return optimize_for(stmt_ptr, arena);
+            }
+        case While_kind:
+            {
+                return optimize_while(stmt_ptr, arena);
+            }
+        case If_kind:
+            {
+                return optimize_if(stmt_ptr, arena);
+            }
+        case With_kind:
+            {
+                return optimize_with(stmt_ptr, arena);
+            }
+        case Raise_kind:
+            {
+                return optimize_raise(stmt_ptr, arena);
+            }
+        case TryExcept_kind:
+            {
+                return optimize_try_except(stmt_ptr, arena);
+            }
+        case TryFinally_kind:
+            {
+                return optimize_try_finally(stmt_ptr, arena);
+            }
+        case Assert_kind:
+            {
+                return optimize_assert(stmt_ptr, arena);
+            }
+        case Import_kind:
+            {
+                return optimize_import(stmt_ptr, arena);
+            }
+        case ImportFrom_kind:
+            {
+                return optimize_import_from(stmt_ptr, arena);
+            }
+        case Exec_kind:
+            {
+                return optimize_exec(stmt_ptr, arena);
+            }
+        case Global_kind:
+            {
+                return optimize_global(stmt_ptr, arena);
+            }
+        case Expr_kind:
+            {
+                return optimize_expr(&stmt->v.Expr.value, arena);
+            }
+        case Pass_kind:
+        case Break_kind:
+        case Continue_kind:
+            {
+                return 1;
+            }
+        default:
+            PyErr_Format(PyExc_ValueError, "unknown stmt_ty kind: %d",
+                    stmt->kind);
+            return 0;
+    };
+
+    return 1;
+}
+
+/**
+ * Optimize an AST.
+ */
+int
+PyAST_Optimize(mod_ty* mod_ptr, PyArena* arena)
+{
+    return optimize_mod(mod_ptr, arena);
+}
+

Modified: python/branches/tlee-ast-optimize/Python/peephole.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/peephole.c	(original)
+++ python/branches/tlee-ast-optimize/Python/peephole.c	Tue Apr 22 12:48:17 2008
@@ -69,164 +69,6 @@
 	return 1;
 }
 
-/* Replace LOAD_CONST c1. LOAD_CONST c2 BINOP
-   with	   LOAD_CONST binop(c1,c2)
-   The consts table must still be in list form so that the
-   new constant can be appended.
-   Called with codestr pointing to the first LOAD_CONST. 
-   Abandons the transformation if the folding fails (i.e.  1+'a').  
-   If the new constant is a sequence, only folds when the size
-   is below a threshold value.	That keeps pyc files from
-   becoming large in the presence of code like:	 (None,)*1000.
-*/
-static int
-fold_binops_on_constants(unsigned char *codestr, PyObject *consts)
-{
-	PyObject *newconst, *v, *w;
-	Py_ssize_t len_consts, size;
-	int opcode;
-
-	/* Pre-conditions */
-	assert(PyList_CheckExact(consts));
-	assert(codestr[0] == LOAD_CONST);
-	assert(codestr[3] == LOAD_CONST);
-
-	/* Create new constant */
-	v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
-	w = PyList_GET_ITEM(consts, GETARG(codestr, 3));
-	opcode = codestr[6];
-	switch (opcode) {
-		case BINARY_POWER:
-			newconst = PyNumber_Power(v, w, Py_None);
-			break;
-		case BINARY_MULTIPLY:
-			newconst = PyNumber_Multiply(v, w);
-			break;
-		case BINARY_DIVIDE:
-			/* Cannot fold this operation statically since
-                           the result can depend on the run-time presence
-                           of the -Qnew flag */
-			return 0;
-		case BINARY_TRUE_DIVIDE:
-			newconst = PyNumber_TrueDivide(v, w);
-			break;
-		case BINARY_FLOOR_DIVIDE:
-			newconst = PyNumber_FloorDivide(v, w);
-			break;
-		case BINARY_MODULO:
-			newconst = PyNumber_Remainder(v, w);
-			break;
-		case BINARY_ADD:
-			newconst = PyNumber_Add(v, w);
-			break;
-		case BINARY_SUBTRACT:
-			newconst = PyNumber_Subtract(v, w);
-			break;
-		case BINARY_SUBSCR:
-			newconst = PyObject_GetItem(v, w);
-			break;
-		case BINARY_LSHIFT:
-			newconst = PyNumber_Lshift(v, w);
-			break;
-		case BINARY_RSHIFT:
-			newconst = PyNumber_Rshift(v, w);
-			break;
-		case BINARY_AND:
-			newconst = PyNumber_And(v, w);
-			break;
-		case BINARY_XOR:
-			newconst = PyNumber_Xor(v, w);
-			break;
-		case BINARY_OR:
-			newconst = PyNumber_Or(v, w);
-			break;
-		default:
-			/* Called with an unknown opcode */
-			PyErr_Format(PyExc_SystemError,
-			     "unexpected binary operation %d on a constant",
-				     opcode);
-			return 0;
-	}
-	if (newconst == NULL) {
-		PyErr_Clear();
-		return 0;
-	}
-	size = PyObject_Size(newconst);
-	if (size == -1)
-		PyErr_Clear();
-	else if (size > 20) {
-		Py_DECREF(newconst);
-		return 0;
-	}
-
-	/* Append folded constant into consts table */
-	len_consts = PyList_GET_SIZE(consts);
-	if (PyList_Append(consts, newconst)) {
-		Py_DECREF(newconst);
-		return 0;
-	}
-	Py_DECREF(newconst);
-
-	/* Write NOP NOP NOP NOP LOAD_CONST newconst */
-	memset(codestr, NOP, 4);
-	codestr[4] = LOAD_CONST;
-	SETARG(codestr, 4, len_consts);
-	return 1;
-}
-
-static int
-fold_unaryops_on_constants(unsigned char *codestr, PyObject *consts)
-{
-	PyObject *newconst=NULL, *v;
-	Py_ssize_t len_consts;
-	int opcode;
-
-	/* Pre-conditions */
-	assert(PyList_CheckExact(consts));
-	assert(codestr[0] == LOAD_CONST);
-
-	/* Create new constant */
-	v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
-	opcode = codestr[3];
-	switch (opcode) {
-		case UNARY_NEGATIVE:
-			/* Preserve the sign of -0.0 */
-			if (PyObject_IsTrue(v) == 1)
-				newconst = PyNumber_Negative(v);
-			break;
-		case UNARY_CONVERT:
-			newconst = PyObject_Repr(v);
-			break;
-		case UNARY_INVERT:
-			newconst = PyNumber_Invert(v);
-			break;
-		default:
-			/* Called with an unknown opcode */
-			PyErr_Format(PyExc_SystemError,
-			     "unexpected unary operation %d on a constant",
-				     opcode);
-			return 0;
-	}
-	if (newconst == NULL) {
-		PyErr_Clear();
-		return 0;
-	}
-
-	/* Append folded constant into consts table */
-	len_consts = PyList_GET_SIZE(consts);
-	if (PyList_Append(consts, newconst)) {
-		Py_DECREF(newconst);
-		return 0;
-	}
-	Py_DECREF(newconst);
-
-	/* Write NOP LOAD_CONST newconst */
-	codestr[0] = NOP;
-	codestr[1] = LOAD_CONST;
-	SETARG(codestr, 1, len_consts);
-	return 1;
-}
-
 static unsigned int *
 markblocks(unsigned char *code, Py_ssize_t len)
 {
@@ -344,24 +186,6 @@
 		cumlc = 0;
 
 		switch (opcode) {
-
-			/* Replace UNARY_NOT JUMP_IF_FALSE POP_TOP with 
-			   with	   JUMP_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;
-
 				/* not a is b -->  a is not b
 				   not a in b -->  a not in b
 				   not a is not b -->  a is b
@@ -399,20 +223,6 @@
 				cumlc = lastlc + 1;
 				break;
 
-				/* Skip over LOAD_CONST trueconst
-                                   JUMP_IF_FALSE xx  POP_TOP */
-			case LOAD_CONST:
-				cumlc = lastlc + 1;
-				j = GETARG(codestr, i);
-				if (codestr[i+3] != JUMP_IF_FALSE  ||
-				    codestr[i+6] != POP_TOP  ||
-				    !ISBASICBLOCK(blocks,i,7)  ||
-				    !PyObject_IsTrue(PyList_GET_ITEM(consts, j)))
-					continue;
-				memset(codestr+i, NOP, 7);
-				cumlc = 0;
-				break;
-
 				/* Try to fold tuples of constants (includes a case for lists
 				   which are only used for "in" and "not in" tests).
 				   Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
@@ -452,44 +262,6 @@
 				}
 				break;
 
-				/* Fold binary ops on constants.
-				   LOAD_CONST c1 LOAD_CONST c2 BINOP -->  LOAD_CONST binop(c1,c2) */
-			case BINARY_POWER:
-			case BINARY_MULTIPLY:
-			case BINARY_TRUE_DIVIDE:
-			case BINARY_FLOOR_DIVIDE:
-			case BINARY_MODULO:
-			case BINARY_ADD:
-			case BINARY_SUBTRACT:
-			case BINARY_SUBSCR:
-			case BINARY_LSHIFT:
-			case BINARY_RSHIFT:
-			case BINARY_AND:
-			case BINARY_XOR:
-			case BINARY_OR:
-				if (lastlc >= 2	 &&
-				    ISBASICBLOCK(blocks, i-6, 7)  &&
-				    fold_binops_on_constants(&codestr[i-6], consts)) {
-					i -= 2;
-					assert(codestr[i] == LOAD_CONST);
-					cumlc = 1;
-				}
-				break;
-
-				/* Fold unary ops on constants.
-				   LOAD_CONST c1  UNARY_OP -->	LOAD_CONST unary_op(c) */
-			case UNARY_NEGATIVE:
-			case UNARY_CONVERT:
-			case UNARY_INVERT:
-				if (lastlc >= 1	 &&
-				    ISBASICBLOCK(blocks, i-3, 4)  &&
-				    fold_unaryops_on_constants(&codestr[i-3], consts))	{
-					i -= 2;
-					assert(codestr[i] == LOAD_CONST);
-					cumlc = 1;
-				}
-				break;
-
 				/* Simplify conditional jump to conditional jump where the
 				   result of the first test implies the success of a similar
 				   test or the failure of the opposite test.
@@ -549,19 +321,6 @@
 
 			case EXTENDED_ARG:
 				goto exitUnchanged;
-
-				/* Replace RETURN LOAD_CONST None RETURN with just RETURN */
-				/* Remove unreachable JUMPs after RETURN */
-			case RETURN_VALUE:
-				if (i+4 >= codelen)
-					continue;
-				if (codestr[i+4] == RETURN_VALUE &&
-				    ISBASICBLOCK(blocks,i,5))
-					memset(codestr+i+1, NOP, 4);
-				else if (UNCONDITIONAL_JUMP(codestr[i+1]) &&
-				         ISBASICBLOCK(blocks,i,4))
-					memset(codestr+i+1, NOP, 3);
-				break;
 		}
 	}
 

Modified: python/branches/tlee-ast-optimize/Python/pythonrun.c
==============================================================================
--- python/branches/tlee-ast-optimize/Python/pythonrun.c	(original)
+++ python/branches/tlee-ast-optimize/Python/pythonrun.c	Tue Apr 22 12:48:17 2008
@@ -32,6 +32,8 @@
 #include "windows.h"
 #endif
 
+#include "optimize.h"
+
 #ifndef Py_REF_DEBUG
 #define PRINT_TOTAL_REFS()
 #else /* Py_REF_DEBUG */
@@ -1383,6 +1385,9 @@
 		}
 		mod = PyAST_FromNode(n, flags, filename, arena);
 		PyNode_Free(n);
+        if (mod != NULL && flags && !(flags->cf_flags & PyCF_NO_OPTIMIZE))
+            if (!PyAST_Optimize(&mod, arena))
+                return NULL;
 		return mod;
 	}
 	else {
@@ -1408,6 +1413,9 @@
 		}
 		mod = PyAST_FromNode(n, flags, filename, arena);
 		PyNode_Free(n);
+        if (mod != NULL && flags && !(flags->cf_flags & PyCF_NO_OPTIMIZE))
+            if (!PyAST_Optimize(&mod, arena))
+                return NULL;
 		return mod;
 	}
 	else {


More information about the Python-checkins mailing list