Jump-To-Jump elimination could be more aggressive. #93223

sweeneyde · 2022-05-25T16:57:34Z

Example:

def f():
    for i in range(5):
        if i > 3:
            print(i)

  1           0 RESUME                   0

  2           2 LOAD_GLOBAL              1 (NULL + range)
             14 LOAD_CONST               1 (5)
             16 CALL                     1
             26 GET_ITER
        >>   28 FOR_ITER                21 (to 72)
             30 STORE_FAST               0 (i)

  3          32 LOAD_FAST                0 (i)
             34 LOAD_CONST               2 (3)
             36 COMPARE_OP               4 (>)
             42 POP_JUMP_FORWARD_IF_FALSE    13 (to 70)     <--------- could be BACKWARD to 28

  4          44 LOAD_GLOBAL              3 (NULL + print)
             56 LOAD_FAST                0 (i)
             58 CALL                     1
             68 POP_TOP
        >>   70 JUMP_BACKWARD           22 (to 28)

  2     >>   72 LOAD_CONST               0 (None)
             74 RETURN_VALUE

Something like this should suffice:

 static bool
 jump_thread(struct instr *inst, struct instr *target, int opcode)
 {
     assert(!IS_VIRTUAL_OPCODE(opcode) || IS_VIRTUAL_JUMP_OPCODE(opcode));
     assert(is_jump(inst));
     assert(is_jump(target));
     // bpo-45773: If inst->i_target == target->i_target, then nothing actually
     // changes (and we fall into an infinite loop):
-    if (inst->i_lineno == target->i_lineno &&
+    if ((inst->i_lineno == target->i_lineno || target->i_lineno == -1) &&
         inst->i_target != target->i_target)
     {
         inst->i_target = target->i_target;
         inst->i_opcode = opcode;
         return true;
     }
     return false;
 }

cc @markshannon @iritkatriel @brandtbucher

The text was updated successfully, but these errors were encountered:

brandtbucher · 2022-05-25T17:37:56Z

I tried something like this a few months ago, but (if I remember correctly) it ended up duplicating a few blocks in test_dis.py. The net effect was more code, not less, and it ended up actually having the same number of jumps in the final output for all code paths (because some paths had to jump over the new blocks now, I think).

I abandoned that experiment because I couldn’t determine the cause of the duplication. I wonder if that’s still the case (or if @iritkatriel knows what the problem might be).

brandtbucher · 2022-05-25T17:45:32Z

(At any rate, I think my experience highlights just how opaque and complex the interactions between the different compiler passes are.)

sweeneyde added type-bug type-feature interpreter-core and removed type-bug labels May 25, 2022

python / cpython Public

Jump-To-Jump elimination could be more aggressive. #93223

Jump-To-Jump elimination could be more aggressive. #93223

sweeneyde commented May 25, 2022

brandtbucher commented May 25, 2022 •

edited

brandtbucher commented May 25, 2022

python / cpython Public

Jump-To-Jump elimination could be more aggressive. #93223

Jump-To-Jump elimination could be more aggressive. #93223

Comments

sweeneyde commented May 25, 2022

brandtbucher commented May 25, 2022 • edited

brandtbucher commented May 25, 2022

brandtbucher commented May 25, 2022 •

edited