bpo-42615: Delete redundant jump instructions that only bypass empty blocks (GH-23733)

* Delete jump instructions that bypass empty blocks

* Add news entry

* Explicitly check for unconditional jump opcodes

Using the is_jump function results in the inclusion of instructions like
returns for which this optimization is not really valid. So, instead
explicitly check that the instruction is an unconditional jump.

* Handle conditional jumps, delete jumps gracefully

* Ensure b_nofallthrough and b_reachable are valid

* Add test for redundant jumps

* Regenerate importlib.h and edit Misc/ACKS

* Fix bad whitespace

2 files changed, 143 insertions, 101 deletions

diff --git a/Python/compile.c b/Python/compile.c
index ae92869fc95..4792733fd58 100644
--- a/Python/compile.c
+++ b/Python/compile.c
@@ -6437,8 +6437,50 @@ optimize_cfg(struct assembler *a, PyObject *consts)
     for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
        if (b->b_reachable == 0) {
             b->b_iused = 0;
+            b->b_nofallthrough = 0;
        }
     }
+    /* Delete jump instructions made redundant by previous step. If a non-empty
+       block ends with a jump instruction, check if the next non-empty block
+       reached through normal flow control is the target of that jump. If it
+       is, then the jump instruction is redundant and can be deleted.
+    */
+    for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
+        if (b->b_iused > 0) {
+            struct instr *b_last_instr = &b->b_instr[b->b_iused - 1];
+            if (b_last_instr->i_opcode == POP_JUMP_IF_FALSE ||
+                b_last_instr->i_opcode == POP_JUMP_IF_TRUE ||
+                b_last_instr->i_opcode == JUMP_ABSOLUTE ||
+                b_last_instr->i_opcode == JUMP_FORWARD) {
+                basicblock *b_next_act = b->b_next;
+                while (b_next_act != NULL && b_next_act->b_iused == 0) {
+                    b_next_act = b_next_act->b_next;
+                }
+                if (b_last_instr->i_target == b_next_act) {
+                    b->b_nofallthrough = 0;
+                    switch(b_last_instr->i_opcode) {
+                        case POP_JUMP_IF_FALSE:
+                        case POP_JUMP_IF_TRUE:
+                            b_last_instr->i_opcode = POP_TOP;
+                            b_last_instr->i_target = NULL;
+                            b_last_instr->i_oparg = 0;
+                            break;
+                        case JUMP_ABSOLUTE:
+                        case JUMP_FORWARD:
+                            b_last_instr->i_opcode = NOP;
+                            clean_basic_block(b);
+                            break;
+                    }
+                    /* The blocks after this one are now reachable through it */
+                    b_next_act = b->b_next;
+                    while (b_next_act != NULL && b_next_act->b_iused == 0) {
+                        b_next_act->b_reachable = 1;
+                        b_next_act = b_next_act->b_next;
+                    }
+                }
+            }
+        }
+    }
     minimize_lineno_table(a);
     return 0;
 }
diff --git a/Python/importlib.h b/Python/importlib.h
index e05c8ea3914..f8def1b2b95 100644
--- a/Python/importlib.h
+++ b/Python/importlib.h
@@ -1749,107 +1749,107 @@ const unsigned char _Py_M__importlib_bootstrap[] = {
     102,114,111,109,95,110,97,109,101,129,4,0,0,115,10,0,
     0,0,10,1,8,1,12,1,8,1,255,128,114,231,0,0,
     0,99,2,0,0,0,0,0,0,0,0,0,0,0,10,0,
-    0,0,5,0,0,0,67,0,0,0,115,164,0,0,0,124,
+    0,0,5,0,0,0,67,0,0,0,115,162,0,0,0,124,
     1,97,0,124,0,97,1,116,2,116,1,131,1,125,2,116,
-    1,106,3,160,4,161,0,68,0,93,70,92,2,125,3,125,
+    1,106,3,160,4,161,0,68,0,93,68,92,2,125,3,125,
     4,116,5,124,4,124,2,131,2,114,26,124,3,116,1,106,
-    6,118,0,114,60,116,7,125,5,110,16,116,0,160,8,124,
-    3,161,1,114,26,116,9,125,5,110,0,116,10,124,4,124,
-    5,131,2,125,6,116,11,124,6,124,4,131,2,1,0,113,
-    26,116,1,106,3,116,12,25,0,125,7,100,1,68,0,93,
-    46,125,8,124,8,116,1,106,3,118,1,114,136,116,13,124,
-    8,131,1,125,9,110,10,116,1,106,3,124,8,25,0,125,
-    9,116,14,124,7,124,8,124,9,131,3,1,0,113,112,100,
-    2,83,0,41,3,122,250,83,101,116,117,112,32,105,109,112,
-    111,114,116,108,105,98,32,98,121,32,105,109,112,111,114,116,
-    105,110,103,32,110,101,101,100,101,100,32,98,117,105,108,116,
-    45,105,110,32,109,111,100,117,108,101,115,32,97,110,100,32,
-    105,110,106,101,99,116,105,110,103,32,116,104,101,109,10,32,
-    32,32,32,105,110,116,111,32,116,104,101,32,103,108,111,98,
-    97,108,32,110,97,109,101,115,112,97,99,101,46,10,10,32,
-    32,32,32,65,115,32,115,121,115,32,105,115,32,110,101,101,
-    100,101,100,32,102,111,114,32,115,121,115,46,109,111,100,117,
-    108,101,115,32,97,99,99,101,115,115,32,97,110,100,32,95,
-    105,109,112,32,105,115,32,110,101,101,100,101,100,32,116,111,
-    32,108,111,97,100,32,98,117,105,108,116,45,105,110,10,32,
-    32,32,32,109,111,100,117,108,101,115,44,32,116,104,111,115,
-    101,32,116,119,111,32,109,111,100,117,108,101,115,32,109,117,
-    115,116,32,98,101,32,101,120,112,108,105,99,105,116,108,121,
-    32,112,97,115,115,101,100,32,105,110,46,10,10,32,32,32,
-    32,41,3,114,26,0,0,0,114,95,0,0,0,114,68,0,
-    0,0,78,41,15,114,61,0,0,0,114,18,0,0,0,114,
-    3,0,0,0,114,99,0,0,0,218,5,105,116,101,109,115,
-    114,203,0,0,0,114,82,0,0,0,114,169,0,0,0,114,
-    92,0,0,0,114,184,0,0,0,114,149,0,0,0,114,155,
-    0,0,0,114,9,0,0,0,114,231,0,0,0,114,12,0,
-    0,0,41,10,218,10,115,121,115,95,109,111,100,117,108,101,
-    218,11,95,105,109,112,95,109,111,100,117,108,101,90,11,109,
-    111,100,117,108,101,95,116,121,112,101,114,20,0,0,0,114,
-    104,0,0,0,114,116,0,0,0,114,103,0,0,0,90,11,
-    115,101,108,102,95,109,111,100,117,108,101,90,12,98,117,105,
-    108,116,105,110,95,110,97,109,101,90,14,98,117,105,108,116,
-    105,110,95,109,111,100,117,108,101,114,5,0,0,0,114,5,
-    0,0,0,114,6,0,0,0,218,6,95,115,101,116,117,112,
-    136,4,0,0,115,40,0,0,0,4,9,4,1,8,3,18,
-    1,10,1,10,1,6,1,10,1,6,1,10,3,10,1,2,
-    128,10,3,8,1,10,1,10,1,10,2,14,1,4,251,255,
-    128,114,235,0,0,0,99,2,0,0,0,0,0,0,0,0,
-    0,0,0,2,0,0,0,3,0,0,0,67,0,0,0,115,
-    38,0,0,0,116,0,124,0,124,1,131,2,1,0,116,1,
-    106,2,160,3,116,4,161,1,1,0,116,1,106,2,160,3,
-    116,5,161,1,1,0,100,1,83,0,41,2,122,48,73,110,
-    115,116,97,108,108,32,105,109,112,111,114,116,101,114,115,32,
-    102,111,114,32,98,117,105,108,116,105,110,32,97,110,100,32,
-    102,114,111,122,101,110,32,109,111,100,117,108,101,115,78,41,
-    6,114,235,0,0,0,114,18,0,0,0,114,201,0,0,0,
-    114,126,0,0,0,114,169,0,0,0,114,184,0,0,0,41,
-    2,114,233,0,0,0,114,234,0,0,0,114,5,0,0,0,
-    114,5,0,0,0,114,6,0,0,0,218,8,95,105,110,115,
-    116,97,108,108,171,4,0,0,115,8,0,0,0,10,2,12,
-    2,16,1,255,128,114,236,0,0,0,99,0,0,0,0,0,
-    0,0,0,0,0,0,0,1,0,0,0,4,0,0,0,67,
-    0,0,0,115,32,0,0,0,100,1,100,2,108,0,125,0,
-    124,0,97,1,124,0,160,2,116,3,106,4,116,5,25,0,
-    161,1,1,0,100,2,83,0,41,3,122,57,73,110,115,116,
-    97,108,108,32,105,109,112,111,114,116,101,114,115,32,116,104,
-    97,116,32,114,101,113,117,105,114,101,32,101,120,116,101,114,
-    110,97,108,32,102,105,108,101,115,121,115,116,101,109,32,97,
-    99,99,101,115,115,114,25,0,0,0,78,41,6,218,26,95,
-    102,114,111,122,101,110,95,105,109,112,111,114,116,108,105,98,
-    95,101,120,116,101,114,110,97,108,114,133,0,0,0,114,236,
-    0,0,0,114,18,0,0,0,114,99,0,0,0,114,9,0,
-    0,0,41,1,114,237,0,0,0,114,5,0,0,0,114,5,
-    0,0,0,114,6,0,0,0,218,27,95,105,110,115,116,97,
-    108,108,95,101,120,116,101,114,110,97,108,95,105,109,112,111,
-    114,116,101,114,115,179,4,0,0,115,8,0,0,0,8,3,
-    4,1,20,1,255,128,114,238,0,0,0,41,2,78,78,41,
-    1,78,41,2,78,114,25,0,0,0,41,4,78,78,114,5,
-    0,0,0,114,25,0,0,0,41,54,114,10,0,0,0,114,
-    7,0,0,0,114,26,0,0,0,114,95,0,0,0,114,68,
-    0,0,0,114,133,0,0,0,114,17,0,0,0,114,21,0,
-    0,0,114,63,0,0,0,114,37,0,0,0,114,47,0,0,
-    0,114,22,0,0,0,114,23,0,0,0,114,53,0,0,0,
-    114,54,0,0,0,114,57,0,0,0,114,69,0,0,0,114,
-    71,0,0,0,114,80,0,0,0,114,90,0,0,0,114,94,
-    0,0,0,114,105,0,0,0,114,118,0,0,0,114,119,0,
-    0,0,114,98,0,0,0,114,149,0,0,0,114,155,0,0,
-    0,114,159,0,0,0,114,114,0,0,0,114,100,0,0,0,
-    114,166,0,0,0,114,167,0,0,0,114,101,0,0,0,114,
-    169,0,0,0,114,184,0,0,0,114,189,0,0,0,114,198,
-    0,0,0,114,200,0,0,0,114,202,0,0,0,114,208,0,
-    0,0,90,15,95,69,82,82,95,77,83,71,95,80,82,69,
-    70,73,88,114,210,0,0,0,114,213,0,0,0,218,6,111,
-    98,106,101,99,116,114,214,0,0,0,114,215,0,0,0,114,
-    216,0,0,0,114,221,0,0,0,114,227,0,0,0,114,230,
-    0,0,0,114,231,0,0,0,114,235,0,0,0,114,236,0,
-    0,0,114,238,0,0,0,114,5,0,0,0,114,5,0,0,
-    0,114,5,0,0,0,114,6,0,0,0,218,8,60,109,111,
-    100,117,108,101,62,1,0,0,0,115,106,0,0,0,4,0,
-    8,22,4,9,4,1,4,1,4,3,8,3,8,8,4,8,
-    4,2,16,3,14,4,14,77,14,21,8,16,8,37,8,17,
-    14,11,8,8,8,11,8,12,8,19,14,36,16,101,10,26,
-    14,45,8,72,8,17,8,17,8,30,8,36,8,45,14,15,
-    14,75,14,80,8,13,8,9,10,9,8,47,4,16,8,1,
-    8,2,6,32,8,3,10,16,14,15,8,37,10,27,8,37,
-    8,7,8,35,12,8,255,128,
+    6,118,0,114,60,116,7,125,5,110,14,116,0,160,8,124,
+    3,161,1,114,26,116,9,125,5,116,10,124,4,124,5,131,
+    2,125,6,116,11,124,6,124,4,131,2,1,0,113,26,116,
+    1,106,3,116,12,25,0,125,7,100,1,68,0,93,46,125,
+    8,124,8,116,1,106,3,118,1,114,134,116,13,124,8,131,
+    1,125,9,110,10,116,1,106,3,124,8,25,0,125,9,116,
+    14,124,7,124,8,124,9,131,3,1,0,113,110,100,2,83,
+    0,41,3,122,250,83,101,116,117,112,32,105,109,112,111,114,
+    116,108,105,98,32,98,121,32,105,109,112,111,114,116,105,110,
+    103,32,110,101,101,100,101,100,32,98,117,105,108,116,45,105,
+    110,32,109,111,100,117,108,101,115,32,97,110,100,32,105,110,
+    106,101,99,116,105,110,103,32,116,104,101,109,10,32,32,32,
+    32,105,110,116,111,32,116,104,101,32,103,108,111,98,97,108,
+    32,110,97,109,101,115,112,97,99,101,46,10,10,32,32,32,
+    32,65,115,32,115,121,115,32,105,115,32,110,101,101,100,101,
+    100,32,102,111,114,32,115,121,115,46,109,111,100,117,108,101,
+    115,32,97,99,99,101,115,115,32,97,110,100,32,95,105,109,
+    112,32,105,115,32,110,101,101,100,101,100,32,116,111,32,108,
+    111,97,100,32,98,117,105,108,116,45,105,110,10,32,32,32,
+    32,109,111,100,117,108,101,115,44,32,116,104,111,115,101,32,
+    116,119,111,32,109,111,100,117,108,101,115,32,109,117,115,116,
+    32,98,101,32,101,120,112,108,105,99,105,116,108,121,32,112,
+    97,115,115,101,100,32,105,110,46,10,10,32,32,32,32,41,
+    3,114,26,0,0,0,114,95,0,0,0,114,68,0,0,0,
+    78,41,15,114,61,0,0,0,114,18,0,0,0,114,3,0,
+    0,0,114,99,0,0,0,218,5,105,116,101,109,115,114,203,
+    0,0,0,114,82,0,0,0,114,169,0,0,0,114,92,0,
+    0,0,114,184,0,0,0,114,149,0,0,0,114,155,0,0,
+    0,114,9,0,0,0,114,231,0,0,0,114,12,0,0,0,
+    41,10,218,10,115,121,115,95,109,111,100,117,108,101,218,11,
+    95,105,109,112,95,109,111,100,117,108,101,90,11,109,111,100,
+    117,108,101,95,116,121,112,101,114,20,0,0,0,114,104,0,
+    0,0,114,116,0,0,0,114,103,0,0,0,90,11,115,101,
+    108,102,95,109,111,100,117,108,101,90,12,98,117,105,108,116,
+    105,110,95,110,97,109,101,90,14,98,117,105,108,116,105,110,
+    95,109,111,100,117,108,101,114,5,0,0,0,114,5,0,0,
+    0,114,6,0,0,0,218,6,95,115,101,116,117,112,136,4,
+    0,0,115,40,0,0,0,4,9,4,1,8,3,18,1,10,
+    1,10,1,6,1,10,1,4,1,10,3,10,1,2,128,10,
+    3,8,1,10,1,10,1,10,2,14,1,4,251,255,128,114,
+    235,0,0,0,99,2,0,0,0,0,0,0,0,0,0,0,
+    0,2,0,0,0,3,0,0,0,67,0,0,0,115,38,0,
+    0,0,116,0,124,0,124,1,131,2,1,0,116,1,106,2,
+    160,3,116,4,161,1,1,0,116,1,106,2,160,3,116,5,
+    161,1,1,0,100,1,83,0,41,2,122,48,73,110,115,116,
+    97,108,108,32,105,109,112,111,114,116,101,114,115,32,102,111,
+    114,32,98,117,105,108,116,105,110,32,97,110,100,32,102,114,
+    111,122,101,110,32,109,111,100,117,108,101,115,78,41,6,114,
+    235,0,0,0,114,18,0,0,0,114,201,0,0,0,114,126,
+    0,0,0,114,169,0,0,0,114,184,0,0,0,41,2,114,
+    233,0,0,0,114,234,0,0,0,114,5,0,0,0,114,5,
+    0,0,0,114,6,0,0,0,218,8,95,105,110,115,116,97,
+    108,108,171,4,0,0,115,8,0,0,0,10,2,12,2,16,
+    1,255,128,114,236,0,0,0,99,0,0,0,0,0,0,0,
+    0,0,0,0,0,1,0,0,0,4,0,0,0,67,0,0,
+    0,115,32,0,0,0,100,1,100,2,108,0,125,0,124,0,
+    97,1,124,0,160,2,116,3,106,4,116,5,25,0,161,1,
+    1,0,100,2,83,0,41,3,122,57,73,110,115,116,97,108,
+    108,32,105,109,112,111,114,116,101,114,115,32,116,104,97,116,
+    32,114,101,113,117,105,114,101,32,101,120,116,101,114,110,97,
+    108,32,102,105,108,101,115,121,115,116,101,109,32,97,99,99,
+    101,115,115,114,25,0,0,0,78,41,6,218,26,95,102,114,
+    111,122,101,110,95,105,109,112,111,114,116,108,105,98,95,101,
+    120,116,101,114,110,97,108,114,133,0,0,0,114,236,0,0,
+    0,114,18,0,0,0,114,99,0,0,0,114,9,0,0,0,
+    41,1,114,237,0,0,0,114,5,0,0,0,114,5,0,0,
+    0,114,6,0,0,0,218,27,95,105,110,115,116,97,108,108,
+    95,101,120,116,101,114,110,97,108,95,105,109,112,111,114,116,
+    101,114,115,179,4,0,0,115,8,0,0,0,8,3,4,1,
+    20,1,255,128,114,238,0,0,0,41,2,78,78,41,1,78,
+    41,2,78,114,25,0,0,0,41,4,78,78,114,5,0,0,
+    0,114,25,0,0,0,41,54,114,10,0,0,0,114,7,0,
+    0,0,114,26,0,0,0,114,95,0,0,0,114,68,0,0,
+    0,114,133,0,0,0,114,17,0,0,0,114,21,0,0,0,
+    114,63,0,0,0,114,37,0,0,0,114,47,0,0,0,114,
+    22,0,0,0,114,23,0,0,0,114,53,0,0,0,114,54,
+    0,0,0,114,57,0,0,0,114,69,0,0,0,114,71,0,
+    0,0,114,80,0,0,0,114,90,0,0,0,114,94,0,0,
+    0,114,105,0,0,0,114,118,0,0,0,114,119,0,0,0,
+    114,98,0,0,0,114,149,0,0,0,114,155,0,0,0,114,
+    159,0,0,0,114,114,0,0,0,114,100,0,0,0,114,166,
+    0,0,0,114,167,0,0,0,114,101,0,0,0,114,169,0,
+    0,0,114,184,0,0,0,114,189,0,0,0,114,198,0,0,
+    0,114,200,0,0,0,114,202,0,0,0,114,208,0,0,0,
+    90,15,95,69,82,82,95,77,83,71,95,80,82,69,70,73,
+    88,114,210,0,0,0,114,213,0,0,0,218,6,111,98,106,
+    101,99,116,114,214,0,0,0,114,215,0,0,0,114,216,0,
+    0,0,114,221,0,0,0,114,227,0,0,0,114,230,0,0,
+    0,114,231,0,0,0,114,235,0,0,0,114,236,0,0,0,
+    114,238,0,0,0,114,5,0,0,0,114,5,0,0,0,114,
+    5,0,0,0,114,6,0,0,0,218,8,60,109,111,100,117,
+    108,101,62,1,0,0,0,115,106,0,0,0,4,0,8,22,
+    4,9,4,1,4,1,4,3,8,3,8,8,4,8,4,2,
+    16,3,14,4,14,77,14,21,8,16,8,37,8,17,14,11,
+    8,8,8,11,8,12,8,19,14,36,16,101,10,26,14,45,
+    8,72,8,17,8,17,8,30,8,36,8,45,14,15,14,75,
+    14,80,8,13,8,9,10,9,8,47,4,16,8,1,8,2,
+    6,32,8,3,10,16,14,15,8,37,10,27,8,37,8,7,
+    8,35,12,8,255,128,
 };