classification
Title: Simplify the deep-first-search of the assembler
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Mark.Shannon, pablogsal, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2019-12-29 03:59 by pablogsal, last changed 2020-06-28 00:56 by pablogsal. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 17733 merged pablogsal, 2019-12-29 05:52
Messages (4)
msg358978 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-29 03:59
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.
msg358989 - (view) Author: Mark Shannon (Mark.Shannon) * (Python committer) Date: 2019-12-29 13:57
This seems correct, but your change assumes that there is no optimisation pass that reorders the blocks.
While the is currently true, it might not be in future.

The code that orders blocks for output should not make assumptions about the shape of the CFG, IMO.
msg358991 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-12-29 16:42
> The code that orders blocks for output should not make assumptions about the shape of the CFG, IMO.

I very much agree with this but notice that technically this function is doing it already if I am not mistaken. Following the b_next pointers in the first for loop already relies on the topological order in which they were emitted.
msg372487 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2020-06-28 00:55
New changeset 60eb9f1ab59a59ddf81d3da3513cfa3251169b5c by Pablo Galindo in branch 'master':
bpo-39151: Simplify DFS in the assembler (GH-17733)
https://github.com/python/cpython/commit/60eb9f1ab59a59ddf81d3da3513cfa3251169b5c
History
Date User Action Args
2020-06-28 00:56:02pablogsalsetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2020-06-28 00:55:53pablogsalsetmessages: + msg372487
2019-12-29 16:42:49pablogsalsetmessages: + msg358991
2019-12-29 13:57:20Mark.Shannonsetmessages: + msg358989
2019-12-29 05:52:11pablogsalsetkeywords: + patch
stage: patch review
pull_requests: + pull_request17178
2019-12-29 03:59:28pablogsalcreate