Repository: python/mypy
Pull request: [mypyc] Remove unused labels and gotos
This PR removes labels which are never jumped to, as well as removing gotos that jump directly to the next label (and removes the now redundant label). I had a small issue with the `GetAttr` op code as it would insert C code after the end of the branch which could not be detected at the IR level, as seen in https://github.com/mypyc/mypyc/issues/600#issuecomment-1319530780 .

Here are some basic stats on the file sizes before and after this PR:

Building with `MYPY_OPT_LEVEL=0`, `MYPY_DEBUG_LEVEL=1`:

| Branch   | `.so` size      | `.c` size       | `.c` lines      |
|----------|-----------------|-----------------|-----------------|
| `master` | 43.9 MB         | 79.7 MB         | 2290675         |
| This PR  | 43.6 MB (-0.6%) | 78.6 MB (-1.4%) | 2179967 (-4.8%) |

Building with `MYPY_OPT_LEVEL=3`, `MYPY_DEBUG_LEVEL=0`:

| Branch   | `.so` size | `.c` size | `.c` lines |
|----------|------------|-----------|------------|
| `master` | 26.5 MB    | 79.7 MB   | 2291316    |
| This PR  | 26.5 MB    | 78.7 MB   | 2179701    |

(I don't know why the number of lines changes between optimization levels. It's only a couple hundred lines, perhaps Mypyc is emitting different code depending on optimization level?)

Unoptimized builds seem to benefit the most, while optimized builds look pretty much the same. I didn't check to see if they are *exactly* the same binary, but they are probably close if not the same. The biggest win is the drop in the number of lines C code being generated.

Closes https://github.com/mypyc/mypyc/issues/600

Problem statement:
Get rid of unnecessary gotos in branches
We often have branches in generated C that look something like this:

```
    if (something)
        goto X;
    else
        goto Y;
Y:
```

We can obviously remove the else part. This may improve compile speed, and this would make the generated C easier to read by humans. 

Sometimes we may be able to also remove the label `Y`, which would be even better.

Hints from issue discussion:
In particular, this may help compile speed and performance when using no C optimizations (`-O0`).
Hi @JukkaL! I attempted to fix this in my [`remove-unused-labels-and-gotos`](https://github.com/dosisod/mypy/tree/remove-unused-labels-and-gotos) branch, but I am running into some problems.

The code that I wrote basically looks at all the `BasicBlock`s in the function, and looks to see which blocks jump to it (excluding the block directly above it). Then, when emitting the C code, it will exclude that label (if it is never jumped to), and will also exclude any `goto` statements that only jump to the block directly below it.

All is well, except that sometimes code is inserted after the `if` statement. The following example is from `master`:

```c
CPyL19: ;
	cpy_r_r35 = 1;
	cpy_r_r36 = ((native___CObject *)cpy_r_c)->_x;
	if (unlikely(cpy_r_r36 == CPY_INT_TAG)) {
		CPy_AttributeError("native.py", "test_delete", "C", "x", 19, CPyStatic_globals);
		goto CPyL21;
	}
	CPyTagged_INCREF(cpy_r_r36);
	goto CPyL77;
CPyL21: ;
```

And this is what my branch spits out:

```c
CPyL19: ;
	cpy_r_r35 = 1;
	cpy_r_r36 = ((native___CObject *)cpy_r_c)->_x;
	if (unlikely(cpy_r_r36 == CPY_INT_TAG)) {
		CPy_AttributeError("native.py", "test_delete", "C", "x", 19, CPyStatic_globals);
	}
	CPyTagged_INCREF(cpy_r_r36);
	goto CPyL77;
/* CPyL21 would normally be here */ 
```

As you can tell, the `goto CPyL21;` line is not emitted anymore, but this changes the control flow because there is the tagging code is being inserted right below to it.

Basically, because of all the extra code being added on *after* the IR has been created, there is no sane way to detect whether the `goto` should be dropped or not.

There is some good news though! Although the emitted code cannot fully be trusted (only 3 tests failed, but still), there are some  stats which you might find interesting:

| Branch | Number of Labels | `__native.c` size (MB) | `mypy.so` size (MB) |
|--------|------------------|------------------------|---------------------|
| master | 230309           | 79.88 MB               | 47.65 MB            |
| mine   | **88440 (-61.6%)** | **78.58 MB (-1.6%)**  | **47.08 MB (-1.2%)** |

What surprised me the most is the ~1% decrease in the final `.so` file. I would've thought the compiler would be smart enough to remove any unused labels, but that does not seem to be the case (or perhaps there is some other factor which causes the decrease).

A (very minor) optimization we could do right now though is remove the `CPyL0` label from every function, since nothing ever jumps to that label. I could open a PR for this, but I thought I would get your opinion on this before I move forward with anything!

Commit message: [mypyc] Remove unused labels and gotos:

This PR removes labels which are never jumped to, as well as removing gotos
that jump directly to the next label (and removes the now redundant label).
I had a small issue with the `GetAttr` op code as it would insert C code after
the end of the branch which could not be detected at the IR level, as seen in
https://github.com/mypyc/mypyc/issues/600#issuecomment-1319530780 .

Here are some basic stats on the file sizes before and after this PR:

Building with `MYPY_OPT_LEVEL=0`, `MYPY_DEBUG_LEVEL=1`:

| Branch   | `.so` size      | `.c` size       | `.c` lines      |
|----------|-----------------|-----------------|-----------------|
| `master` | 43.9 MB         | 79.7 MB         | 2290675         |
| This PR  | 43.6 MB (-0.6%) | 78.6 MB (-1.4%) | 2179967 (-4.8%) |

Building with `MYPY_OPT_LEVEL=3`, `MYPY_DEBUG_LEVEL=0`:

| Branch   | `.so` size | `.c` size | `.c` lines |
|----------|------------|-----------|------------|
| `master` | 26.5 MB    | 79.7 MB   | 2291316    |
| This PR  | 26.5 MB    | 78.7 MB   | 2179701    |

(I don't know why the number of lines changes between optimization levels.
It's only a couple hundred lines, perhaps Mypyc is emitting different code
depending on optimization level?)

Unoptimized builds seem to benefit the most, while optimized builds look
prety much the same. I didn't check to see if they are *exactly* the same
binary, but they are probably close if not the same. The biggest win is the
drop in the number of lines C code being generated.

Closes https://github.com/mypyc/mypyc/issues/600

Patch to review:
diff --git a/mypyc/codegen/emit.py b/mypyc/codegen/emit.py
index 56ce9637307b..a2e3d9849dca 100644
--- a/mypyc/codegen/emit.py
+++ b/mypyc/codegen/emit.py
@@ -229,6 +229,9 @@ def emit_label(self, label: BasicBlock | str) -> None:
         if isinstance(label, str):
             text = label
         else:
+            if label.label == 0 or not label.referenced:
+                return
+
             text = self.label(label)
         # Extra semicolon prevents an error when the next line declares a tempvar
         self.fragments.append(f"{text}: ;\n")
diff --git a/mypyc/codegen/emitfunc.py b/mypyc/codegen/emitfunc.py
index f2406ff1a257..e37c2825c55f 100644
--- a/mypyc/codegen/emitfunc.py
+++ b/mypyc/codegen/emitfunc.py
@@ -23,6 +23,7 @@
     CallC,
     Cast,
     ComparisonOp,
+    ControlOp,
     DecRef,
     Extend,
     Float,
@@ -123,6 +124,25 @@ def generate_native_function(
     for i, block in enumerate(blocks):
         block.label = i
 
+    for block in fn.blocks:
+        terminator = block.terminator
+        assert isinstance(terminator, ControlOp)
+
+        for bb in terminator.targets():
+            is_next_block = bb.label == block.label + 1
+
+            # Always emit labels for GetAttr op codes since the emit code that
+            # generates them will add instructions between the branch and the
+            # next label, causing the label to be wrongly removed. A better
+            # solution would be to change the IR so that it adds a basic block
+            # inbetween the calls.
+            is_problematic_op = isinstance(terminator, Branch) and any(
+                isinstance(s, GetAttr) for s in terminator.sources()
+            )
+
+            if not is_next_block or is_problematic_op:
+                fn.blocks[bb.label].referenced = True
+
     common = frequently_executed_blocks(fn.blocks[0])
 
     for i in range(len(blocks)):
@@ -216,7 +236,8 @@ def visit_branch(self, op: Branch) -> None:
 
         if false is self.next_block:
             if op.traceback_entry is None:
-                self.emit_line(f"if ({cond}) goto {self.label(true)};")
+                if true is not self.next_block:
+                    self.emit_line(f"if ({cond}) goto {self.label(true)};")
             else:
                 self.emit_line(f"if ({cond}) {{")
                 self.emit_traceback(op)
@@ -224,9 +245,11 @@ def visit_branch(self, op: Branch) -> None:
         else:
             self.emit_line(f"if ({cond}) {{")
             self.emit_traceback(op)
-            self.emit_lines(
-                "goto %s;" % self.label(true), "} else", "    goto %s;" % self.label(false)
-            )
+
+            if true is not self.next_block:
+                self.emit_line("goto %s;" % self.label(true))
+
+            self.emit_lines("} else", "    goto %s;" % self.label(false))
 
     def visit_return(self, op: Return) -> None:
         value_str = self.reg(op.value)
diff --git a/mypyc/ir/ops.py b/mypyc/ir/ops.py
index 351f7c01efe2..6007f8a4ce04 100644
--- a/mypyc/ir/ops.py
+++ b/mypyc/ir/ops.py
@@ -81,6 +81,7 @@ def __init__(self, label: int = -1) -> None:
         self.label = label
         self.ops: list[Op] = []
         self.error_handler: BasicBlock | None = None
+        self.referenced = False
 
     @property
     def terminated(self) -> bool:
diff --git a/mypyc/test/test_emitfunc.py b/mypyc/test/test_emitfunc.py
index d7dcf3be532b..ab1586bb22a8 100644
--- a/mypyc/test/test_emitfunc.py
+++ b/mypyc/test/test_emitfunc.py
@@ -894,12 +894,7 @@ def test_simple(self) -> None:
         generate_native_function(fn, emitter, "prog.py", "prog")
         result = emitter.fragments
         assert_string_arrays_equal(
-            [
-                "CPyTagged CPyDef_myfunc(CPyTagged cpy_r_arg) {\n",
-                "CPyL0: ;\n",
-                "    return cpy_r_arg;\n",
-                "}\n",
-            ],
+            ["CPyTagged CPyDef_myfunc(CPyTagged cpy_r_arg) {\n", "    return cpy_r_arg;\n", "}\n"],
             result,
             msg="Generated code invalid",
         )
@@ -922,7 +917,6 @@ def test_register(self) -> None:
             [
                 "PyObject *CPyDef_myfunc(CPyTagged cpy_r_arg) {\n",
                 "    CPyTagged cpy_r_r0;\n",
-                "CPyL0: ;\n",
                 "    cpy_r_r0 = 10;\n",
                 "    CPy_Unreachable();\n",
                 "}\n",


Code review comments:
diff_hunk: @@ -123,6 +124,25 @@ def generate_native_function(
     for i, block in enumerate(blocks):
         block.label = i
 
+    for block in fn.blocks:
+        terminator = block.terminator
+        assert isinstance(terminator, ControlOp)
+
+        for bb in terminator.targets():
path: mypyc/codegen/emitfunc.py
text: @user1:
`bb` isn't that clear of a variable name IMO. Not sure what to rename it to though...

@author:
Yeah, I was using `bb` for `BasicBlock` which wasn't very descriptive. Since we are iterating using `targets()` I renamed it to `target` instead.