8000 Compile constant tuples to constant objects immediately in the parser by dpgeorge · Pull Request #8504 · micropython/micropython · GitHub
[go: up one dir, main page]

Skip to content

Compile constant tuples to constant objects immediately in the parser #8504

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 17 commits into from
Apr 14, 2022
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
17 commits
Select commit Hold shift + click to select a range
42d0bd2
py/persistentcode: Define enum values for obj types instead of letters.
dpgeorge Apr 7, 2022
e52f14d
py/parse: Factor obj extract code to mp_parse_node_extract_const_object.
dpgeorge Mar 31, 2022
24bc1f6
py/parse: Print const object value in mp_parse_node_print.
dpgeorge Mar 31, 2022
35c0cff
py/parse: Add MICROPY_COMP_CONST_TUPLE option to build const tuples.
dpgeorge Mar 31, 2022
4ca9698
py/persistentcode: Support loading and saving tuples in .mpy files.
dpgeorge Mar 31, 2022
2a075cc
tools/mpy-tool.py: Support loading tuples from .mpy files.
dpgeorge Mar 31, 2022
68b3aee
tools/mpy-tool.py: Support freezing tuples and other consts.
dpgeorge Mar 31, 2022
24894f9
ports: Recompile bytecode tests now that .mpy format changed.
dpgeorge Apr 7, 2022
999abbb
tests/perf_bench: Update import tests for changes to .mpy consts.
dpgeorge Apr 8, 2022
abdc4ec
qemu-arm/test-frzmpy: Add test for freezing constant tuples.
dpgeorge Apr 7, 2022
9c8a563
tools/mpy-tool.py: Optimise freezing of ints that can fit a small int.
dpgeorge Apr 7, 2022
dfc6c62
tools/mpy-tool.py: Optimise freezing of empty str and bytes objects.
dpgeorge Apr 8, 2022
e647966
tools/mpy-tool.py: Make global qstr list a dedicated class.
dpgeorge Apr 8, 2022
40d431d
tools/mpy-tool.py: Optimise freezing of str when str data is a qstr.
dpgeorge Apr 8, 2022
07f5260
tools/mpy-tool.py: Intern more strings when freezing.
dpgeorge Apr 8, 2022
865b61d
tests/micropython: Add tests that const tuples don't use the heap.
dpgeorge Apr 11, 2022
9ab66b5
docs/reference: Update constrained docs now that tuples can be const.
dpgeorge Apr 11, 2022
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
27 changes: 16 additions & 11 deletions docs/reference/constrained.rst
Original file line number Diff line number Diff line change
Expand Up @@ -126,8 +126,9 @@ that the objects remain in flash memory rather than being copied to RAM. The
Python built-in types.

When considering the implications of frozen bytecode, note that in Python
strings, floats, bytes, integers and complex numbers are immutable. Accordingly
these will be frozen into flash. Thus, in the line
strings, floats, bytes, integers, complex numbers and tuples are immutable.
Accordingly these will be frozen into flash (for tuples, only if all their
elements are immutable). Thus, in the line

.. code::

Expand All @@ -146,16 +147,16 @@ As in the string example, at runtime a reference to the arbitrarily large
integer is assigned to the variable ``bar``. That reference occupies a
single machine word.

It might be expected that tuples of integers could be employed for the purpose
of storing constant data with minimal RAM use. With the current compiler this
is ineffective (the code works, but RAM is not saved).
Tuples of constant objects are themselves constant. Such constant tuples are
optimised by the compiler so they do not need to be created at runtime each time
they are used. For example:

.. code::

foo = (1, 2, 3, 4, 5, 6, 100000)
foo = (1, 2, 3, 4, 5, 6, 100000, ("string", b"bytes", False, True))

At runtime the tuple will be located in RAM. This may be subject to future
improvement.
This entire tuple will exist as a single object (potentially in flash if the
code is frozen) and referenced each time it is needed.

**Needless object creation**

Expand Down Expand Up @@ -214,20 +215,24 @@ buffer; this is both faster and more efficient in terms of memory fragmentation.

**Bytes are smaller than ints**

On most platforms an integer consumes four bytes. Consider the two calls to the
On most platforms an integer consumes four bytes. Consider the three calls to the
function ``foo()``:

.. code::

def foo(bar):
for x in bar:
print(x)
foo([1, 2, 0xff])
foo((1, 2, 0xff))
foo(b'\1\2\xff')

In the first call a tuple of integers is created in RAM. The second efficiently
In the first call a `list` of integers is created in RAM each time the code is
executed. The second call creates a constant `tuple` object (a `tuple` containing
only constant objects) as part of the compilation phase, so it is only created
once and is more efficient than the `list`. The third call efficiently
creates a `bytes` object consuming the minimum amount of RAM. If the module
were frozen as bytecode, the `bytes` object would reside in flash.
were frozen as bytecode, both the `tuple` and `bytes` object would reside in flash.

**Strings Versus Bytes**

Expand Down
Binary file modified ports/minimal/frozentest.mpy
Binary file not shown.
Binary file modified ports/powerpc/frozentest.mpy
Binary file not shown.
11 changes: 11 additions & 0 deletions ports/qemu-arm/test-frzmpy/frozen_const.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,11 @@
# Test freezing constants.

x0 = (1,)
x1 = (1, 2)
x2 = (1, 1 << 100)
x3 = (None, False, True, ...)
x4 = ("str", b"bytes")
x5 = ((),)
x6 = ((1,),)
x7 = ((1, 2),)
x8 = (1, "str", (), ("nested", 2, ((False, True), None, ...)))
7 changes: 1 addition & 6 deletions py/compile.c
Original file line number Diff line number Diff line change
Expand Up @@ -2763,12 +2763,7 @@ STATIC void compile_atom_expr_await(compiler_t *comp, mp_parse_node_struct_t *pn
#endif

STATIC mp_obj_t get_const_object(mp_parse_node_struct_t *pns) {
#if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
// nodes are 32-bit pointers, but need to extract 64-bit object
return (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
#else
return (mp_obj_t)pns->nodes[0];
#endif
return mp_parse_node_extract_const_object(pns);
}

STATIC void compile_const_object(compiler_t *comp, mp_parse_node_struct_t *pns) {
Expand Down
6 changes: 6 additions & 0 deletions py/mpconfig.h
Original file line number Diff line number Diff line change
Expand Up @@ -441,6 +441,12 @@
#define MICROPY_COMP_CONST_FOLDING (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_CORE_FEATURES)
#endif

// Whether to compile constant tuples immediately to their respective objects; eg (1, True)
// Otherwise the tuple will be built at runtime
#ifndef MICROPY_COMP_CONST_TUPLE
#define MICROPY_COMP_CONST_TUPLE (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_CORE_FEATURES)
#endif

// Whether to enable optimisations for constant literals, eg OrderedDict
#ifndef MICROPY_COMP_CONST_LITERAL
#define MICROPY_COMP_CONST_LITERAL (MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_CORE_FEATURES)
Expand Down
161 changes: 153 additions & 8 deletions py/parse.c
Original file line number Diff line number Diff line change
Expand Up @@ -291,6 +291,16 @@ STATIC void *parser_alloc(parser_t *parser, size_t num_bytes) {
return ret;
}

#if MICROPY_COMP_CONST_TUPLE
STATIC void parser_free_parse_node_struct(parser_t *parser, mp_parse_node_struct_t *pns) {
mp_parse_chunk_t *chunk = parser->cur_chunk;
if (chunk->data <= (byte *)pns && (byte *)pns < chunk->data + chunk->union_.used) {
size_t num_bytes = sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
chunk->union_.used -= num_bytes;
}
}
#endif

STATIC void push_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t arg_i) {
if (parser->rule_stack_top >= parser->rule_stack_alloc) {
rule_stack_t *rs = m_renew(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc + MICROPY_ALLOC_PARSE_RULE_INC);
Expand All @@ -317,6 +327,13 @@ STATIC uint8_t pop_rule(parser_t *parser, size_t *arg_i, size_t *src_line) {
return rule_id;
}

#if MICROPY_COMP_CONST_TUPLE
STATIC uint8_t peek_rule(parser_t *parser, size_t n) {
assert(parser->rule_stack_top > n);
return parser->rule_stack[parser->rule_stack_top - 1 - n].rule_id;
}
#endif

bool mp_parse_node_is_const_false(mp_parse_node_t pn) {
return MP_PARSE_NODE_IS_TOKEN_KIND(pn, MP_TOKEN_KW_FALSE)
|| (MP_PARSE_NODE_IS_SMALL_INT(pn) && MP_PARSE_NODE_LEAF_SMALL_INT(pn) == 0);
Expand All @@ -333,18 +350,83 @@ bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o) {
return true;
} else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
#if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
// nodes are 32-bit pointers, but need to extract 64-bit object
*o = (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
#else
*o = (mp_obj_t)pns->nodes[0];
#endif
*o = mp_parse_node_extract_const_object(pns);
return mp_obj_is_int(*o);
} else {
return false;
}
}

#if MICROPY_COMP_CONST_TUPLE
STATIC bool mp_parse_node_is_const(mp_parse_node_t pn) {
if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
// Small integer.
return true;
} else if (MP_PARSE_NODE_IS_LEAF(pn)) {
// Possible str, or constant literal.
uintptr_t kind = MP_PARSE_NODE_LEAF_KIND(pn);
if (kind == MP_PARSE_NODE_STRING) {
return true;
} else if (kind == MP_PARSE_NODE_TOKEN) {
uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
return arg == MP_TOKEN_KW_NONE
|| arg == MP_TOKEN_KW_FALSE
|| arg == MP_TOKEN_KW_TRUE
|| arg == MP_TOKEN_ELLIPSIS;
}
} else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
// Constant object.
return true;
} else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_atom_paren)) {
// Possible empty tuple.
mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
return MP_PARSE_NODE_IS_NULL(pns->nodes[0]);
}
return false;
}

STATIC mp_obj_t mp_parse_node_convert_to_obj(mp_parse_node_t pn) {
assert(mp_parse_node_is_const(pn));
if (MP_PARSE_NODE_IS_SMALL_INT(pn)) {
mp_int_t arg = MP_PARSE_NODE_LEAF_SMALL_INT(pn);
#if MICROPY_DYNAMIC_COMPILER
mp_uint_t sign_mask = -((mp_uint_t)1 << (mp_dynamic_compiler.small_int_bits - 1));
if (!((arg & sign_mask) == 0 || (arg & sign_mask) == sign_mask)) {
// Integer doesn't fit in a small-int, so create a multi-precision int object.
return mp_obj_new_int_from_ll(arg);
}
#endif
return MP_OBJ_NEW_SMALL_INT(arg);
} else if (MP_PARSE_NODE_IS_LEAF(pn)) {
uintptr_t kind = MP_PARSE_NODE_LEAF_KIND(pn);
uintptr_t arg = MP_PARSE_NODE_LEAF_ARG(pn);
if (kind == MP_PARSE_NODE_STRING) {
return MP_OBJ_NEW_QSTR(arg);
} else {
assert(MP_PARSE_NODE_LEAF_KIND(pn) == MP_PARSE_NODE_TOKEN);
switch (arg) {
case MP_TOKEN_KW_NONE:
return mp_const_none;
case MP_TOKEN_KW_FALSE:
return mp_const_false;
case MP_TOKEN_KW_TRUE:
return mp_const_true;
default:
assert(arg == MP_TOKEN_ELLIPSIS);
return MP_OBJ_FROM_PTR(&mp_const_ellipsis_obj);
}
}
} else if (MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_const_object)) {
mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
return mp_parse_node_extract_const_object(pns);
} else {
assert(MP_PARSE_NODE_IS_STRUCT_KIND(pn, RULE_atom_paren));
assert(MP_PARSE_NODE_IS_NULL(((mp_parse_node_struct_t *)pn)->nodes[0]));
return mp_const_empty_tuple;
}
}
#endif

size_t mp_parse_node_extract_list(mp_parse_node_t *pn, size_t pn_kind, mp_parse_node_t **nodes) {
if (MP_PARSE_NODE_IS_NULL(*pn)) {
*nodes = NULL;
Expand Down Expand Up @@ -397,11 +479,14 @@ void mp_parse_node_print(const mp_print_t *print, mp_parse_node_t pn, size_t ind
// node must be a mp_parse_node_struct_t
mp_parse_node_struct_t *pns = (mp_parse_node_struct_t *)pn;
if (MP_PARSE_NODE_STRUCT_KIND(pns) == RULE_const_object) {
mp_obj_t obj = mp_parse_node_extract_const_object(pns);
#if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
mp_printf(print, "literal const(%016llx)\n", (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32));
mp_printf(print, "literal const(%016llx)=", obj);
#else
mp_printf(print, "literal const(%p)\n", (mp_obj_t)pns->nodes[0]);
mp_printf(print, "literal const(%p)=", obj);
#endif
mp_obj_print_helper(print, obj, PRINT_REPR);
mp_printf(print, "\n");
} else {
size_t n = MP_PARSE_NODE_STRUCT_NUM_NODES(pns);
#if MICROPY_DEBUG_PARSE_RULE_NAME
Expand Down Expand Up @@ -793,6 +878,59 @@ STATIC bool fold_constants(parser_t *parser, uint8_t rule_id, size_t num_args) {
}
#endif

#if MICROPY_COMP_CONST_TUPLE
STATIC bool build_tuple_from_stack(parser_t *parser, size_t src_line, size_t num_args) {
for (size_t i = num_args; i > 0;) {
mp_parse_node_t pn = peek_result(parser, --i);
if (!mp_parse_node_is_const(pn)) {
return false;
}
}
mp_obj_tuple_t *tuple = MP_OBJ_TO_PTR(mp_obj_new_tuple(num_args, NULL));
for (size_t i = num_args; i > 0;) {
mp_parse_node_t pn = pop_result(parser);
tuple->items[--i] = mp_parse_node_convert_to_obj(pn);
if (MP_PARSE_NODE_IS_STRUCT(pn)) {
parser_free_parse_node_struct(parser, (mp_parse_node_struct_t *)pn);
}
}
push_result_node(parser, make_node_const_object(parser, src_line, MP_OBJ_FROM_PTR(tuple)));
return true;
}

STATIC bool build_tuple(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args) {
if (rule_id == RULE_testlist_comp) {
if (peek_rule(parser, 0) == RULE_atom_paren) {
// Tuple of the form "(a,)".
return build_tuple_from_stack(parser, src_line, num_args);
}
}
if (rule_id == RULE_testlist_comp_3c) {
assert(peek_rule(parser, 0) == RULE_testlist_comp_3b);
assert(peek_rule(parser, 1) == RULE_testlist_comp);
if (peek_rule(parser, 2) == RULE_atom_paren) {
// Tuple of the form "(a, b)".
if (build_tuple_from_stack(parser, src_line, num_args)) {
parser->rule_stack_top -= 2; // discard 2 rules
return true;
}
}
}
if (rule_id == RULE_testlist_star_expr
|| rule_id == RULE_testlist
|| rule_id == RULE_subscriptlist) {
// Tuple of the form:
// - x = a, b
// - return a, b
// - for x in a, b: pass
// - x[a, b]
return build_tuple_from_stack(parser, src_line, num_args);
}

return false;
}
#endif

STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id, size_t num_args) {
// Simplify and optimise certain rules, to reduce memory usage and simplify the compiler.
if (rule_id == RULE_atom_paren) {
Expand Down Expand Up @@ -849,6 +987,13 @@ STATIC void push_result_rule(parser_t *parser, size_t src_line, uint8_t rule_id,
}
#endif

#if MICROPY_COMP_CONST_TUPLE
if (build_tuple(parser, src_line, rule_id, num_args)) {
// we built a tuple from this rule so return straightaway
return;
}
#endif

mp_parse_node_struct_t *pn = parser_alloc(parser, sizeof(mp_parse_node_struct_t) + sizeof(mp_parse_node_t) * num_args);
pn->source_line = src_line;
pn->kind_num_nodes = (rule_id & 0xff) | (num_args << 8);
Expand Down
11 changes: 11 additions & 0 deletions py/parse.h
Original file line number Diff line number Diff line change
Expand Up @@ -77,9 +77,20 @@ typedef struct _mp_parse_node_struct_t {
static inline mp_parse_node_t mp_parse_node_new_small_int(mp_int_t val) {
return (mp_parse_node_t)(MP_PARSE_NODE_SMALL_INT | ((mp_uint_t)val << 1));
}

static inline mp_parse_node_t mp_parse_node_new_leaf(size_t kind, mp_int_t arg) {
return (mp_parse_node_t)(kind | ((mp_uint_t)arg << 4));
}

static inline mp_obj_t mp_parse_node_extract_const_object(mp_parse_node_struct_t *pns) {
#if MICROPY_OBJ_REPR == MICROPY_OBJ_REPR_D
// nodes are 32-bit pointers, but need to extract 64-bit object
return (uint64_t)pns->nodes[0] | ((uint64_t)pns->nodes[1] << 32);
#else
return (mp_obj_t)pns->nodes[0];
#endif
}

bool mp_parse_node_is_const_false(mp_parse_node_t pn);
bool mp_parse_node_is_const_true(mp_parse_node_t pn);
bool mp_parse_node_get_int_maybe(mp_parse_node_t pn, mp_obj_t *o);
Expand Down
Loading
0