[New-bugs-announce] [issue39151] Simplify the deep-first-search of the assembler

[Pablo Galindo Salgado]

New submission from Pablo Galindo Salgado <pablogsal at gmail.com>:

I was recently checking the code of the assembler and when looking in detail at the dfs() function I was surprised by this code:

static void
dfs(struct compiler *c, basicblock *b, struct assembler *a, int end)
{
....

    while (j < end) {
        b = a->a_postorder[j++];
        for (i = 0; i < b->b_iused; i++) {
            struct instr *instr = &b->b_instr[i];
            if (instr->i_jrel || instr->i_jabs)
                dfs(c, instr->i_target, a, j);
        }
        assert(a->a_nblocks < j);
        a->a_postorder[a->a_nblocks++] = b;
    }
}

In particular, the recursive call to:

dfs(c, instr->i_target, a, j)

I cannot imagine a situation in which the previous for loop

    for (j = end; b && !b->b_seen; b = b->b_next) {
        b->b_seen = 1;
        assert(a->a_nblocks < j);
        a->a_postorder[--j] = b;
    }

has not visited all blocks (so the b_seen is already set) and in which the recursion will do something meaninfull. Indeed, as a naive check, simplifying the function to (no recursive call):

static void
dfs(struct compiler *c, basicblock *b, struct assembler *a, int end)
{
    int i, j;

    for (j = end; b && !b->b_seen; b = b->b_next) {
        b->b_seen = 1;
        assert(a->a_nblocks < j);
        a->a_postorder[--j] = b;
    }
    while (j < end) {
        b = a->a_postorder[j++];
        assert(a->a_nblocks < j);
        a->a_postorder[a->a_nblocks++] = b;
    }
}

passes the full test suite. I am missing something? Even if I am missing something I think that situation should be added to the test suite so It mativated me to open the issue.

----------
components: Interpreter Core
messages: 358978
nosy: Mark.Shannon, pablogsal, serhiy.storchaka
priority: normal
severity: normal
status: open
title: Simplify the deep-first-search of the assembler
type: behavior
versions: Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue39151>
_______________________________________