# Stability of Python bytecode and its compiler for domain-specific extension of Python

## Background

- Growing interest and new libraries that are domain-specific extensions of Python
- optimizing compilers:
- HPC; numeric/loop/array/tensor-oriented programming
- code transformers
- autodiff in machine-learning, deep-learning
- Bytecode is the only program representation that is always available. ([details on why AST is insufficient?](#Why-the-AST-is-insufficient))
- Deep-learning usecases rely on auto-differentiation which become easier if user source code can be accessed or reconstructed.

## Capturing user intent

- Python bytecode perfectly models the execution semantic but optimizing compilers and code transformers operate better when user intent can be reconstructed.
- Optimizing compilers work by removing unneeded effects. Python optimized bytecode blurs the separation of user-intended effects vs internal "plumbing" effects for the Python VM.
- Optimizing compilers and code transformers need to reconstruct the control-flow structure for specific transformations. They may have limited support for structured control-flow constructs. Bytecode optimization can easily convert an accepted control-flow structure into an unsupported structure. When bytecode optimization becomes more advanced, we may lose the ability to reconstruct. (See example [here](#Example-Bytecode-optimization-inlines-return-block) and [here](#Example-Large-dictionary))

## Possible solutions:

1. Exposing an unoptimized IR along with the code object.
- https://bugs.python.org/issue42926 is a related proposal. Splitting the bytecode compiler and allowing access to the unoptimized intermediate representation will help.
- This unoptimized IR is closer to the original user source code.
- This can become the canonical representation of Python source, allowing in other tools. Avoiding the need for AST extension or custom IR, such as `typed_ast`.

2. Providing access to the AST during compilation.
- [PEP-638: Syntactic Macros](https://peps.python.org/pep-0638/) proposes a mechanism for this.
- Less attractive solution because this is less flexible than an always accessible IR.
- Our usecases can be satisfied by just having the compiler plugin portion of the PEP if the syntax change for spelling the macros is too big of a change.

## Extras

### Example: Bytecode optimization inlines return block

Python 3.10 begins to optimize short exiting blocks by duplicating the exit block into originating block. This optimization is the most recent example that complicated the reconstruction of the for-loop because the exit block is fused with the block that `break`. A domain-specific extension may forbid the use of the `return` statement inside a loop.

import dis


def for_loop_inline_exit(n):
    x = 1
    for i in range(n):
        if some_check(i):
            x = 2
            break
        x += i
    return x


dis.dis(for_loop_inline_exit)

Py3.9

  5           0 LOAD_CONST               1 (1)
              2 STORE_FAST               1 (x)

  6           4 LOAD_GLOBAL              0 (range)
              6 LOAD_FAST                0 (n)
              8 CALL_FUNCTION            1
             10 GET_ITER
        >>   12 FOR_ITER                28 (to 42)
             14 STORE_FAST               2 (i)

  7          16 LOAD_GLOBAL              1 (some_check)
             18 LOAD_FAST                2 (i)
             20 CALL_FUNCTION            1
             22 POP_JUMP_IF_FALSE       32

  8          24 LOAD_CONST               2 (2)
             26 STORE_FAST               1 (x)

  9          28 POP_TOP
             30 JUMP_ABSOLUTE           42

 10     >>   32 LOAD_FAST                1 (x)
             34 LOAD_FAST                2 (i)
             36 INPLACE_ADD
             38 STORE_FAST               1 (x)
             40 JUMP_ABSOLUTE           12

 11     >>   42 LOAD_FAST                1 (x)
             44 RETURN_VALUE

Py3.10
Note: There are two `RETURN_VALUE`.

  5           0 LOAD_CONST               1 (1)
              2 STORE_FAST               1 (x)

  6           4 LOAD_GLOBAL              0 (range)
              6 LOAD_FAST                0 (n)
              8 CALL_FUNCTION            1
             10 GET_ITER
        >>   12 FOR_ITER                15 (to 44)
             14 STORE_FAST               2 (i)

  7          16 LOAD_GLOBAL              1 (some_check)
             18 LOAD_FAST                2 (i)
             20 CALL_FUNCTION            1
             22 POP_JUMP_IF_FALSE       17 (to 34)

  8          24 LOAD_CONST               2 (2)
             26 STORE_FAST               1 (x)

  9          28 POP_TOP

 11          30 LOAD_FAST                1 (x)
             32 RETURN_VALUE

 10     >>   34 LOAD_FAST                1 (x)
             36 LOAD_FAST                2 (i)
             38 INPLACE_ADD
             40 STORE_FAST               1 (x)
             42 JUMP_ABSOLUTE            6 (to 12)

 11     >>   44 LOAD_FAST                1 (x)
             46 RETURN_VALUE
             

### Example: Large dictionary

Related issue: [numba#7894](https://github.com/numba/numba/issues/7894)

Construction of large dictionary is now written as:

def f():
    d = {
        "a": 1,
        "b": 2,
        "c": 3,
        "d": 4,
        "e": 5,
        "f": 6,
        "g": 7,
        "h": 8,
        "i": 9,
        "j": 10,
        "k": 11,
        "l": 12,
        "m": 13,
        "n": 14,
        "o": 15,
        "p": 16,
        "q": 17,
        "r": 18,
        "s": 19,
    }
    return d

Python 3.9 bytecode:

  5           0 LOAD_CONST               1 (1)

  6           2 LOAD_CONST               2 (2)
  ...
 23          36 LOAD_CONST              19 (19)

  4          38 LOAD_CONST              20 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's'))
             40 BUILD_CONST_KEY_MAP     19
             42 STORE_FAST               0 (d)

 25          44 LOAD_FAST                0 (d)
             46 RETURN_VALUE

In Python 3.9, the dictionary is built from loading constant key-value mapping (`BUILD_CONST_KEY_MAP`).

Python 3.10 bytecode:

4           0 BUILD_MAP                0

  5           2 LOAD_CONST               1 ('a')
              4 LOAD_CONST               2 (1)

  4           6 MAP_ADD                  1

  6           8 LOAD_CONST               3 ('b')
             10 LOAD_CONST               4 (2)

  4          12 MAP_ADD                  1
  ...
 22         104 LOAD_CONST              35 (18)

 23         106 LOAD_CONST              36 (19)

  4         108 LOAD_CONST              37 (('r', 's'))
            110 BUILD_CONST_KEY_MAP      2
            112 DICT_UPDATE              1
            114 STORE_FAST               0 (d)

 25         116 LOAD_FAST                0 (d)
            118 RETURN_VALUE

In Python 3.10, the dictionary is created by a mix of inserting (`MAP_ADD`) each key-value pair and combining a dictionary following the approach in Python 3.9. With this approach, we cannot easily rule out that the dictionary is never mutated in the code.

### Why the AST is insufficient?

Source code is not always available; e.g. source-stripped packages with only .pyc files, dynamically created code (`exec`), distributed execution of user-defined functions, serialized functions that are reconstituted in another process.