bpo-29469: Move constant folding at AST level

python · methane · Dec 14, 2017 · Jul 25, 2017 · Jul 26, 2017 · Jul 26, 2017
commit b0c47450cd48b5a4042424f90b1fa609fad73e75
diff --git a/Include/compile.h b/Include/compile.h
@@ -75,6 +75,8 @@ PyAPI_FUNC(PyObject*) _Py_Mangle(PyObject *p, PyObject *name);
 #define PY_INVALID_STACK_EFFECT INT_MAX
 PyAPI_FUNC(int) PyCompile_OpcodeStackEffect(int opcode, int oparg);
 
+PyAPI_FUNC(int) _PyAST_Optimize(struct _mod *, PyArena *arena);
+
 #ifdef __cplusplus
 }
 #endif

diff --git a/Makefile.pre.in b/Makefile.pre.in
@@ -320,6 +320,7 @@ PYTHON_OBJS=	\
 		Python/Python-ast.o \
 		Python/asdl.o \
 		Python/ast.o \
+		Python/ast_opt.o \
 		Python/bltinmodule.o \
 		Python/ceval.o \
 		Python/compile.o \
@@ -799,6 +800,10 @@ regen-ast:
 	$(PYTHON_FOR_REGEN) $(srcdir)/Parser/asdl_c.py \
 		-c $(srcdir)/Python \
 		$(srcdir)/Parser/Python.asdl
+	$(PYTHON_FOR_REGEN) $(srcdir)/Parser/asdl_ct.py \
+		$(srcdir)/Parser/Python.asdl \
+		$(srcdir)/Python/ast_opt.ct \
+		$(srcdir)/Python/ast_opt.c
 
 .PHONY: regen-opcode
 regen-opcode:

diff --git a/Misc/NEWS.d/next/Core and Builtins/2017-07-26-00-20-15.bpo-29469.potmyI.rst b/Misc/NEWS.d/next/Core and Builtins/2017-07-26-00-20-15.bpo-29469.potmyI.rst
@@ -0,0 +1,2 @@
+Move constant folding from bytecode layer to AST layer.
+Original patch by Eugene Toder.
diff --git a/PCbuild/pythoncore.vcxproj b/PCbuild/pythoncore.vcxproj
@@ -352,6 +352,7 @@
     <ClCompile Include="..\Python\_warnings.c" />
     <ClCompile Include="..\Python\asdl.c" />
     <ClCompile Include="..\Python\ast.c" />
+    <ClCompile Include="..\Python\ast_opt.c" />
     <ClCompile Include="..\Python\bltinmodule.c" />
     <ClCompile Include="..\Python\bootstrap_hash.c" />
     <ClCompile Include="..\Python\ceval.c" />

diff --git a/PCbuild/pythoncore.vcxproj.filters b/PCbuild/pythoncore.vcxproj.filters
@@ -842,6 +842,9 @@
     <ClCompile Include="..\Python\ast.c">
       <Filter>Python</Filter>
     </ClCompile>
+    <ClCompile Include="..\Python\ast_opt.c">
+      <Filter>Python</Filter>
+    </ClCompile>
     <ClCompile Include="..\Python\bltinmodule.c">
       <Filter>Python</Filter>
     </ClCompile>

diff --git a/Parser/asdl_ct.py b/Parser/asdl_ct.py
@@ -0,0 +1,289 @@
+#!/usr/bin/env python3
+"Generate code for AST visitors."
+
+import asdl
+import os
+import re
+import sys
+
+def is_reachable(ty, types, rules):
+    "Are any 'rules' reachable from 'ty' given 'types'."
+
+    visited = set()
+    def reachable(ty):
+        if ty in visited:
+            return False
+        visited.add(ty)
+
+        if isinstance(ty, str):
+            if ty in rules:
+                return True
+            return ty in types
+        if isinstance(ty, asdl.Sum):
+            return any(map(reachable, ty.types))
+        elif isinstance(ty, asdl.Constructor):
+            if ty.name in rules:
+                return True
+            return any(reachable(field.type) for field in ty.fields)
+        elif isinstance(ty, asdl.Product):
+            return any(reachable(field.type) for field in ty.fields)
+        else:
+            raise TypeError(type(ty))
+
+        return False
+
+    return reachable(ty)
+
+
+def is_simple(sum):
+    """Return True if a sum is a simple.
+
+    A sum is simple if its types have no fields, e.g.
+    unaryop = Invert | Not | UAdd | USub
+    """
+    for t in sum.types:
+        if t.fields:
+            return False
+    return True
+
+
+
+MACRO_DEF = """
+#define CALL(FUNC, TYPE, ARG) \\
+    if (!FUNC((ARG){0})) \\
+        return 0;
+
+#define CALL_OPT(FUNC, TYPE, ARG) \\
+    if ((ARG) != NULL && !FUNC((ARG){0})) \\
+        return 0;
+
+#define CALL_SEQ(FUNC, TYPE, ARG) {{ \\
+    int i; \\
+    asdl_seq *seq = (ARG); /* avoid variable capture */ \\
+    for (i = 0; i < asdl_seq_LEN(seq); i++) {{ \\
+        TYPE elt = (TYPE)asdl_seq_GET(seq, i); \\
+        if (elt != NULL && !FUNC(elt{0})) \\
+            return 0; \\
+    }} \\
+}}
+
+#define CALL_INT_SEQ(FUNC, TYPE, ARG) {{ \\
+    int i; \\
+    asdl_int_seq *seq = (ARG); /* avoid variable capture */ \\
+    for (i = 0; i < asdl_seq_LEN(seq); i++) {{ \\
+        TYPE elt = (TYPE)asdl_seq_GET(seq, i); \\
+        if (!FUNC(elt{0})) \\
+            return 0; \\
+    }} \\
+}}
+"""
+
+MACRO_UNDEF = """
+#undef CALL
+#undef CALL_OPT
+#undef CALL_SEQ
+"""
+
+BANNER = '/* File automatically generated by Parser/asdl_ct.py and {}. */\n'
+
+class Visitor:
+    "One visitor definition."
+
+    def __init__(self, name, types):
+        self.name = name
+        self.types = types
+        self.rules = {}
+        self._funcs = {}
+
+    def add_rule(self, name, func, kind):
+        "Add @kind(name, func) rule."
+
+        if self._funcs:
+            raise RuntimeError('Visitor already generated.')
+        if name in self.rules:
+            raise NameError('{0} already registered to {1}'
+                                .format(name, self.rules[name]))
+        self.rules[name] = (func, kind)
+
+    def generate(self, out, start, ctx):
+        "Generate visitor function."
+
+        arg = ', ctx_' if ctx else ''
+        out(MACRO_DEF.format(arg), depth=0)
+
+        self._ctx = ctx
+        self._reach = {}
+        self._stack = []
+        self._need_func(start)
+        while self._stack:
+            self._process(out, self._stack.pop())
+
+        out(MACRO_UNDEF, depth=0)
+
+    def write_protos(self, out):
+        "Write prototypes for generated functions."
+
+        if not self._funcs:
+            raise RuntimeError('Visitor not generated.')
+
+        for proto in self._funcs.values():
+            out(proto + ';', depth=0)
+
+    def used(self):
+        return bool(self._funcs)
+
+    def _process(self, out, name):
+        def worker():
+            node = self.types[name]
+            if isinstance(node, (asdl.Constructor, asdl.Product)):
+                self._process_case(out, node, nodety, depth=1)
+            elif isinstance(node, asdl.Sum):
+                if is_simple(node):
+                    out('switch (node_) {', depth=1)
+                else:
+                    out('switch (node_->kind) {', depth=1)
+                for ty in node.types:
+                    if self._can_reach(ty):
+                        out('case ' + ty.name + '_kind:', depth=1)
+                        self._process_case(out, ty, nodety, depth=2)
+                        out('break;', depth=2)
+                out('default:', depth=1)
+                out('break;', depth=2)
+                out('}', depth=1)
+            else:
+                raise TypeError(type(node))
+
+        out(self._funcs[name], depth=0)
+        out('{', depth=0)
+        nodety = name + '_ty'
+        self._with_kind(out, name, nodety, 'node_', worker, depth=1)
+        out('return 1;\n}\n', depth=1)
+
+    def _process_case(self, out, node, nodety, depth):
+        assert isinstance(node, (asdl.Constructor, asdl.Product))
+        def worker():
+            for field in node.fields:
+                ty = field.type
+                assert isinstance(ty, str)
+                if not self._can_reach(ty):
+                    continue
+                func_name = self._need_func(ty)
+                nodety = ty + "_ty"
+                if field.opt:
+                    kind = 'OPT'
+                elif field.seq:
+                    if field.type == 'cmpop':
+                        kind = 'INT_SEQ'
+                    else:
+                        kind = 'SEQ'
+                else:
+                    kind = ''
+                self._call(out, func_name, kind, nodety, prefix + field.name,
+                           depth=depth)
+
+        if isinstance(node, asdl.Constructor):
+            name = node.name
+            prefix = 'node_->v.' + name + '.'
+        else:
+            name = ''
+            prefix = 'node_->'
+        self._with_kind(out, name, nodety, 'node_', worker, depth=depth)
+
+    def _with_kind(self, out, name, nodety, arg, func, depth):
+        rule, kind = self.rules.get(name, (None, None))
+        if kind in ('pre', 'just'):
+            self._call(out, rule, '', nodety, arg, depth=depth)
+        if kind != 'just':
+            func()
+        if kind == 'post':
+            self._call(out, rule, '', nodety, arg, depth=depth)
+
+    def _can_reach(self, ty):
+        if ty in self._reach:
+            return self._reach[ty]
+        self._reach[ty] = can = is_reachable(ty, self.types, self.rules)
+        return can
+
+    def _call(self, out, func, kind, type, arg, depth):
+        if kind:
+            kind = '_' + kind
+        out('CALL{0}({1}, {2}, {3});'.format(kind, func, type, arg),
+            depth=depth)
+
+    def _need_func(self, name):
+        func_name = self.name + '_' + name
+        if name not in self._funcs:
+            proto = "static int {0}({1}_ty node_".format(func_name, name)
+            if self._ctx:
+                proto += ', ' + self._ctx + ' ctx_'
+            proto += ')'
+            self._funcs[name] = proto
+            self._stack.append(name)
+        return func_name
+
+
+class Processor:
+    def __init__(self, asdl_name):
+        self.mod = asdl.parse(asdl_name)
+        self.visitors = {}
+
+    def process(self, infile, outfile):
+        with open(infile) as f:
+            s = re.sub('@(\w+)\(((?:[^,()]*,?)*)\)\n',
+                       self._action, f.read())
+        with open(outfile, 'w') as f:
+            f.write(BANNER.format(os.path.basename(infile)))
+            f.write(s)
+        self._warn()
+
+    def _action(self, match):
+        cmd = match.group(1)
+        args = list(map(str.strip, match.group(2).split(',')))
+        if cmd in ('pre', 'post', 'just'):
+            if len(args) != 3:
+                raise TypeError(cmd + ' expects 3 arguments')
+
+            v = self.visitors.setdefault(args[0],
+                                         Visitor(args[0], self.mod.types))
+            v.add_rule(args[1], args[2], cmd)
+            return ''
+        if cmd == 'visitor':
+            if len(args) < 3:
+                raise TypeError(cmd + ' expects at least 3 arguments')
+            if args[0] not in self.visitors:
+                raise KeyError('visitor ' + args[0] + ' is not defined')
+
+            return self._gen(self.visitors[args[0]], args[2:], args[1])
+
+        raise NameError('unknown command ' + cmd)
+
+    def _gen(self, visitor, starts, ctx):
+        def output(s, depth):
+            out.append('    ' * depth + s)
+
+        out = []
+        for start in starts:
+            visitor.generate(output, start, ctx)
+        code = '\n'.join(out)
+
+        out = []
+        visitor.write_protos(output)
+        protos = '\n'.join(out)
+        return protos + code
+
+    def _warn(self):
+        for v in self.visitors.values():
+            if not v.used():
+                sys.stderr.write('warning: unused visitor ' +
+                                 v.name + '\n')
+
+
+if __name__ == "__main__":
+    args = sys.argv
+    if len(args) != 4:
+        sys.stdout.write("usage: {0} <asdl> <infile> <outfile> \n"
+                          .format(args[0]))
+        sys.exit(1)
+    p = Processor(args[1])
+    p.process(args[2], args[3])
+
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		Move constant folding from bytecode layer to AST layer.
		Original patch by Eugene Toder.